# -*- coding: utf-8 -*-


"""
Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:
Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
As long as a house is in the heaters' warm radius range, it can be warmed.
All the heaters follow your radius standard and the warm radius will the same.
Example 1:
Input: [1,2,3],[2]
Output: 1
Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.
Example 2:
Input: [1,2,3,4],[1,4]
Output: 1
Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.


"""

import bisect


class Solution(object):
    def findRadius(self, houses, heaters):
        """
        :type houses: List[int]
        :type heaters: List[int]
        :rtype: int
        """

        houses = list(sorted(houses))
        heaters = list(sorted(heaters))
        ret = 0

        lh = len(houses)
        s = 0
        for i in range(len(heaters) - 1):
            s = bisect.bisect(houses, heaters[i], s, lh)
            t = bisect.bisect(houses, heaters[i+1], s, lh) - 1

            # ...heaters[i]...houses[s]...houses[t]...heaters[i+1]...
            if s == len(houses):
                break

            if t > s:
                # all houses heated by heaters[i] or heaters[i+1]
                r = min(heaters[i+1]-houses[s], houses[t]-heaters[i])

                for j in range(s, t):
                    # houses[s:j+1] heated by heaters[i] and houses[j+1:t+1] heated by heaters[i+1]
                    r = min(r, max(abs(houses[j] - heaters[i]), abs(houses[j+1] - heaters[i + 1])))
                ret = max(ret, r)
            elif t == s:
                ret = max(ret, min(abs(houses[s]-heaters[i]), abs(houses[s]-heaters[i+1])))

        # houses at left side of heaters[0] must be heated by heaters[0]
        ret = max(ret, heaters[0] - houses[0])

        # houses at right side of heaters[-1] must be heated by heaters[-1]
        ret = max(ret, houses[-1] - heaters[-1])

        return ret

s = Solution()
print(s.findRadius([1,2,3,5,15], [2,30]))
print(s.findRadius([1,2,3], [1,2,3]))

houses = [1, 5, 12, 22]
heaters = [3, 15]
print(s.findRadius(houses, heaters))

print(s.findRadius([1,2,3],[2]))

houses = [282475249,622650073,984943658,144108930,470211272,101027544,457850878,458777923,7237709,823564440,115438165,784484492,74243042,114807987,137522503,441282327,16531729,823378840,143542612,896544303,474833169,264817709,998097157,817129560,131570933,197493099,404280278,893351816,505795335,954899097,636807826,563613512,101929267,580723810,704877633,358580979,624379149,128236579,784558821,530511967,110010672,551901393,617819336,399125485,156091745,356425228,899894091,585640194,937186357,646035001,25921153,510616708,590357944,771515668,357571490,44788124,927702196,952509530,130060903,942727722,83454666,108728549,685118024,118797801,60806853,571540977,194847408,35308228,158374933,75260298,824938981,595028635,962408013,137623865,997389814,20739063,107554536,635339425,654001669,777724115,269220094,34075629,478446501,864546517,351934195,581030105,557810404,146319451,908194298,500782188,657821123,753799505,102246882,269406752,816731566,884936716,807130337,578354438,892053144,153851501,4844897,616783871,382955828,330111137,227619358,723153177,70982397,147722294,70477904,51621609,606946231,190959745,912844175,341853635,808266298,343098142,456880399,534827968,280090412,195400260,589673557,6441594,889688008,57716395,524325968,14119113,515204530,388471006,681910962,904797942,400285365,322842082,463179852,828530767,832633821,73185695,316824712,260973671,815859901,267248590,51724831,194314738,318153057,111631616,877819790,304555640,213110679,541437335,49077006,996497972,63936098,270649095,428975319,685583454,351345223,272112289,398556760,334948905,724586126,532236123,23129506,836045813,436476770,60935238,936329094,915896220,304987844,34712366,881140534,281725226,901915394,197941363,348318738,152607844,784559590,543436550,290145159,681808623,977764947,750597385,971307217,737195272,755539,399399247,462242385,459413496,951894885,537140623,848682420,12028144,86531968,289335735,755699915,623161625,992663534,43046042,358796011,943454679,771024152,479575244,507977295,119878818,49590396,828087692,621301815,154112991,104740033,222122669,889119397,238489553,882410547,944975825,567121210,866729662,536830211,719533808,517273377,592822761,41000625,902737335,127401868,994977995,140002776,532062767,49997439,433829874,464689331,428540556,968456301,859468872,911300560,168120094,298918984,967113755,124639789,462851407,957828015,678030193,105222769,893015680,944303455,4016855,732267506,784170963,454233502,145586676,329863108,353963249,323602331,1277844,1887638,660760808,561939997,685428651,897054849,465645203,461495731,440796531,796198014,522395419,779636775,203042009,175530180,640687929,351995223,459244054,458588260,174076737,834991545,44747317,34837525,837204200,578134256,486421564,609960597,668306648,683337704,907225550,605925150,416541976,24301412,411938554,111482797,524102504,760348381,293034748,855007065,290659378,379847699,778878209,338725129,121578553,552265483,501650447,218264607,471180773,363045322,494664305,706755176,495170053,616927224,437784630,360280366,121205400,284660444,487495370,684570285,502883016,252193898,637608155,129841133,189515557,262696576,707953178,509658266,307187357,347221711,42227878,847320614,746474819,195795737,586983133,678620591,290623720,135048762,667306633,262976197,112576031,925238588,555860589,795054873,843998877,959637304,21979358,832861200,599777254,168068960,794014915,545293947,442645480,452207730,103669955,564674546,547837107,28841238,989340000,18984926,690545035,988774857,110561113,420250114,862929593,300601360,118498354,322968418,439025357,738342585,163313729,122721015,780776563,32106102,588860917,380786643,172819419,971062967,572547747,83245269,529855395,812423303,490404473,978719103,754711748,47424385,345205658,518163459,520045406,937673930,250739824,614285132,129300973,493959603,600246897,618907920,367603950,9135231,64488480,171620203,350213900,939824520,681462533,603481258,937217003,13618676,255820950,113423934,143558780,168279879,836941832,463482574,828433549,346174542,415306249,523252771,156766310,601915879,752200983,798669970,473392040,666082723,20073650,222902971,118753229,666190318,473917746,118710299,151687230,344185621,554270776,637850124,108668244,26076958,981747696,116666771,958829064,322791560,614056598,790318751,493869940,240764503,462789551,711192801,123427205,119315080,164780418,3559274,838659649,63040413,810783320,51519025,237322012,586901783,458854788,151624117,76424008,263081550,90265324,404319195,754451257,318824511,304835690,270438666,187262410,48760593,766490553,799809565,92190960,556228742,540151403,911254352,746007307,928256141,525244910,633413200,492192799,970343127,566120171,429157787,250334414,450031625,244116641,174619517,13055348,377901842,287114315,927515974,177181445,476211373,805972220,795739911,265509239,90245054,63641305,172556929,61382253,652354189,5815166,537204356,772359304,651659860,73645898,609005592,442901720,463866116,625151580,78098867,495149352,476026939,208178698,401494901,324160811,797716616,482756891,501848671,402331728,356326671,597951661,343077045,102303120,421620240,268317158,38299453,39769627,333685350,962853711,38535563,274629594,550207533,66401727,115307827,948398795,114919531,657737442,140351516,950885006,98478515,4466924,706642601,957627097,596168661,440967103,368034324,799980108,18044936,72002281,547517015,151043710,265963216,130301905,343775973,111767781,225882720,807270791,791481169,910297865,702715827,532329536,238616728,872357125,628320384,796580167,502789949,835500476,8416046,300521576,777568666,158577467,977260520,862627384,516341991,178425210,905333258,14428211,622268744,225419518,464685718,722321934,132666825,436280767,854658689,523449818,528073014,566211825,822102918,173958028,987333029,500078034,708006727,55151240,6933754,571486540,427408396,913090935,401203083,69048048,287846865,709087011,31615252,367553064,301377876,137017237,746232675,628070245,94482710,773470415,791728192,560024710,707454747,722463037,356701299,97368447,88949715,329241693,647259579,132567129,115195164,995333979,473553501,439295525,191110289,502574958,517114033,62211800,562165089,528087670,812535217,430880846,499521038,936509543,8240338,849385936,98603321,954597719,73536496,124791247,67943788,617428359,270425987,767145035,707765235,498383912,152185684,924745989,866683784,120263734,76422667,826500519,862972615,669167045,318665976,142326661,373365825,5182819,1271631,483422903,751072698,162936798,230092639,341914004,29909503,763800679,333748765,88207391,737904107,236264924,207314365,114057121,48114454,205777106,840127450,110051703,448530832,583071032,499932141,48961654,412281977,440942217,742753900,142357289,302173465,978084747,476003622,816289879,258459317,359301516,56564048,484182762,637121029,532649039,166052708,266605903,987502657,996510761,924375752,86561466,785108621,974044557,292006996,554426955,115266930,54021494,346645555,96192221,233429312,586802293,141231427,500142232,432477444,209234791,178402198,311549152,434444856,63273570,227464303,264627439,947712914,324735799,78626766,570591835,67981921,110846043,121122752,688574086,75289719,526439150,230168410,822418623,185044669,282409605,312349943,8437311,657922431,101977992,45139816,396138699,496786971,875180639,45501370,30325836,525679891,147182857,594094833,300383328,601518177,510474410,139217683,14885176,505523489,887972091,283070434,681484711,976226904,463491026,763464891,132610790,494500522,308559364,931706890,539924884,399116813,10341441,9907127,591316179,844185784,598994537,45329870,88387561,264032581,894374165,508545802,937357732,231367332,645347854,214459759,947609847,739972377,637940462,626979010,726943819,710298150,119413377,230900941,42143836,434826720,245832299,92396112,856734759,56219956,788974390,728536152,348330048,342695014,123959044,320514918,5240150,817350101,897741295,910819821,885295731,398644501,662128245,129154961,748946057,927703510,974593928,935350805,653662173,366782137,229309669,67439096,725004503,121447421,850318675,595278518,867224300,260276489,835740262,743532054,128868263,18358643,902024889,245245250,608776735,891469415,726031364,407052494,595850963,543867758,887985652,156485092,524957316,887766714,771761420,192958060,345807450,895063368,207078741,448891847,208199196,746004787,885902501,652188234,364093128,925270571,886377448,44687875,242817253,810641871,821669329,476562293,261433719,164973471,307738820,25725764,521681079,511142630,839594410,95688080,350266113,462863342,951398138,778248382,845146044,705698828,920998393,157863575,70800980,39109000,967945596,73005947,590767370,3266087,644506543,313952733,236262852,172490261,88376824,876554400,511982380,68370778,789871857,425373423,278059498,421567014,728252845,236261662,945468509,257726610,929596849,790709218,821019290,288775055,922285743,319518555,439236385,137606534,499086275,864877321,823811151,759921226,703775251,803694459,20632783,30316714,372366437,388337879,384907698,715914100,810383137,768094285,836445878,717918284,489470342,311164915,626045960,432063067,834735140,675810707,309543566,293320728,12000562,977466363,820241969,109242890,739712623,567222278,624917313,790245761,267127010,362834840,104576978,983646000,809207394,334734507,623187656,430166551,24761786,706993431,204554544,619880739,892408776,688507584,105074252,544374108,808275514,497991454,998595019,801783028,107466671,158592370,434756663,215867947,785684024,907424543,802916854,629306008,389114981,767780552,5986288,265768163,792508359,994411019,348255379,28195356,871419461,108408487,955308353,279743899,606985788,855794244,281369880,224582466,428738283,789665274,248300236,414318909,108898567,40621834,978847939,418069684,78169651,123289549,598709266,545747467,268000110,797619589,792486327,417097773,568625581,380889295,750607936,148637874,426245435,694558231,866566972,949983028,971319798,594139070,43874587,251766297,893369089,796102646,67029090,714958111,129966612,150957463,756872112,996923781,423551951,522329230,21703321,281453213,270655128,530371950,904228600,421288959,349949754,795289992,293655194,338403330,801048632,442353559,840858777,871067779,433118632,248263272,86383,451839081,350237153,976132622,233398521,69297956,754609818,836275591,796366900,420400196,237874120,128762704,598733599,600207129,950527144,378859175,197140870,926818416,131204599,275947080,70874618,483764288,46279452,222648128,923552800,933087662,478744840,436279149,34486385,585066583,33924515,524630659,47114878,24245959,272918561,64668382,840728048,466884054,15049440,680351381,108218770,61702028,377340251,231367544,294405869,277117595,770872469,77722710,408508172,84605923,130552125,254256219,939298850,436461431,596111243,830447846,840725869,784766670,521841394,265094610,564026392,391731064,432109524,822559361,48439519,226693620,403681562,775171661,674303725,544479434,431005949,247622090,754137322,337486260,627260093,363159928,480385122,441716381,869226366,903766468,244171023,734112722,938966639,502463517,791608793,700769364,823359178,606061956,568356771,364988341,145751355,157160836,144768489,610979728,262467120,353474902,912910312,660439616,458633347,931853946,71032851,995702672,227725811,571846523,35191736,702482605,553029607,459380633,606587866,817391553,446941412,993997925,640814040,324059153,236634257,765221733,949588295,424988139,245042251,698961258,499292694,39194160,606251138,245949929,921919875,405804598,742794292,821225633,461814562,711443276,38193236,963590646,686783873,844929464,567627484,785742192,885054119,278333842,737499328,23078859,777800262,756044145,173205716,228127127,667292172,812908748,59344000,755174370,380261398,934961292,756589545,749808928,604612300,973792143,344652192,598973563,338314783,667344272,541069801,314384009,835246221,675614486,306624513,270415769,802432531,286245357,562345819,270649486,435546856,611739816,152364254,985509754,68549814,503962615,424166537,468762966,174647297,834458877,327625760,258077412,737580191,27638231,97754174,129412463,781814877,303180324,720494784,488527833,857306750,286759527,407044999,115377429,118199609,744412144,888155364,68372451,232032812,92651979,862124134,441132407,791793583,511567600,539614259,266388310,477900753,489115891,3379321,961673225,879965253,3613929,48236096,102730553,808530661,845784858,704827491,308822963,712542920,340040768,404181687,383816526,556455472,55835219,119655641,446138204,379382951,203288092,809458445,259181370,964449474,295741962,257996176,165225317,38525826,903958413,175223344,778662571,216485979,642551035,807468129,960657288,777959848,83700978,746505617,713417723,803447838,963619508,378888929,490194926,751829968,5471806,415825199,862332255,998559829,3323276,812703488,111527896,489102819,931161864,117091137,294192416,984580318,479904491,599180683,878918398,588991120,67119748,652689961,413705651,746311018,590275977,541379946,877518661,685931478,551112228,239225063,359225235,714971506,591308,348178968,743955679,13304119,57007323,137349677,684079392,842378953,296356978,857151853,830889295,817708271,120548475,981140204,643966962,628128032,65708819,147483531,145534035,592609468,751152468,710652610,427350234,290067270,165706778,540506265,432969045,236143279,103289075,605675327,305712687,125225363,714659037,191375766,314974534,229803083,124818675,528926184,227559555,718044156,457517399,148963664,813852093,881757886,713120633,312244924,597888047,421400194,864971330,256336767,192825665,61106910,319631682,986056805,318396314,550579652,85176241,332973585,737637591,51897806,368064760,311517960,910200912,220710403,568463430,803101085,785214200,808048585,185984467,252230484,898003988,237955200,698495686,471380100,211145495,872328199,142161102,92804428,129367183,20793917,236507136,130687802,180074489,500456578,273239725,20020789,127446722,955860595,971340605,943842319,843638691,141420721,179617774,266898514,817469862,408575706,426671283,409334626,89916419,982723801,342194330,298897644,608452375,89423258,284101462,830103131,135046736,987760720,38808308,2161024,606086947,988380508,925188411,860019397,426556000,826278314,630361896,748533999,444695645,549592533,467514962,674280539,361813754,477558821,977694286,355976536,8200010,378614662,382578173,425314493,435106635,448374988,111284571,694506838,2804821,688964891,201098413,869250560,955889957,317344092,400258743,22889775,894832768,419330413,437900415,365816636,34519891,355223347,234254369,775654832,205024134,69828928,527195143,51240879,64510906,903039054,903425807,961132537,175535203,370604421,45927447,748951034,11351949,252119416,178767759,13081938,617778550,713635183,370352186,101581096,816959685,778470524,76697922,10260363,647229181,976173012,912233251,811472202,537635495,576061536,802933454,908302208,521446980,871608031,130220830,128632095,196566714,866913112,679612136,568629937,661122009,397215685,624842919,332884381,385869610,702899908,331211609,395899439,977532867,144996119,348811266,988074999,878444520,66974515,359242577,213459922,116197142,301203980,716335881,663826885,760910030,349756325,691812436,815146994,377343945,293452602,80923233,719628480,167963456,168292834,54676517,618198881,542708781,943433458,414362805,699174992,3574160,88848651,216616201,683708542,51953944,750049635,355207555,116321872,250057443,89947322,63637013,686378441,473284781,217885779,546669518,939547160,521861729,606864955,179459082,894729364,828903032,439819313,197459195,627434328,937022504,832619855,631437711,502403881,143811610,561099904,805392551,643177616,600996761,129948864,645645405,920432122,377965113,996004943,220048636,390585118,854052994,80952188,999253743,928517639,625274502,351070343,94655070,168336219,783848212,117703317,407209932,94427782,643274097,868047859,69447073,113335590,806244819,82344010,414780911,490853015,281934978,925228542,179996045,182048270,668560562,655903008,521273983,111531099,897440709,153838213,136018550,579642951,73254665,476003502,607251617,28614953,481135299,958017916,367707584,750911869,607367442,34823503,956041515,510074329,857507257,361713382,938090264,451109352,177605154,800532526,565116027,732378755,506449259,415002952,720707386,121267422,972559129,303243786,432595549,46741879,759229198,810278890,163498603,82414686,602632443,703568827,629293585,973300198,873488587,524470817,508134031,459173476,419867461,874131563,593550214,736906383,647386832,478329722,49325511,671132791,937682871,46506142,92164733,115431553,880378030,351222380,709478704,24864915,292798887,978837110,236066681,170411558,156848786,195111433,823304040,33862659,839521936,877617562,200676938,20949754,501154526,266233526,23929712,607227595,831898621,601581177,214810341,190369158,576783054,251606020,347077197,760864727,735832451,570659462,411610332,890022937,391900804,137446057,156454405,9200907,813799943,212294258,59256539,285217343,464383697,941222281,758332965,134181457,915875605,751490117,943068412,721485624,109190184,646861459,238320299,185242216,307614740,87796851,73387846,566892922,177376893,466138615,371358049,827251361,804493649,567717231,353657796,839326123,527050696,918487444,698995250,70596238,538472431,610059359,180715935,543821265,106577801,44718387,755632437,843563948,885215120,43815424,966423894,60542775,221127903,142934989,860116286,261990845,731634143,876657257,93216332,171313261,279385578,234157104,81384202,463157031,444978220,210884686,783878630,628938643,657262367,100205648,115103844,253497317,714829749,120070125,176941273,734607863,463845416,277246680,438415348,430360979,352050957,602986814,424052705,703072189,872233307,694794905,194874527,343613614,530483715,635179308,110398897,841369449,863997495,714456029,281409026,675487866,118984398,49458985,766946662,668677518,474098853,808070579,348616203,650113383,851810723,256830559,902053221,721421174,25979034,483422675,747240702,183089436,633063279,260542915,18594750,929813013,921788850,558172492,996502948,84083,413182981,197225847,207543208,458232706,433710178,600442306,401158267,108804114,600633910,680984470,11127358,186428617,127124946,990222304,460977656,677949663,544733637,615449898,585191734,635348656,16168508,954153012,982259113,915096280,538276724,615779104,468684613,5252073,17739962,448292979,87464377,927948269,793291147,58805631,89719753,972325633,319338739,564552520,851451194,656677597,654889424,665836871,975984958,899093320,366488948,389628018,593437401,781320517,584406392,675512613,387423580,257691356,691587940,129988594,165903868,912535670,806282463,360521649,28965134,924176425,31439871,714891891,809985650,529981217,779630010,89342654,490916525,201863901,849905494,93396392,50098034,770024970,866192546,99456187,610836121,143831565,896483589,454412971,866954865,233871160,777512110,208040775,437928109,831269694,768623323,931031534,74118474,754634414,895155494,755440423,556846875,984673077,891421357,272825627,295705222,433485574,120490172,587198839,9024039,343168183,279554417,924350530,455633890,705082606,508594896,969502012,461885895,555831938,313517516,511505321,285869684,483839227,158295578,889024460,435861972,465443487,573243635,687111581,57750526,536439194,590162030,419251295,462669258,43933419,802082212,633863443,469492312,902368706,581326628,453526593,794963926,108431226,337482726,360842733,982972981,235195296,557429392,37618061,886559009,155721377,219596124,375150522,935814240,59701052,520717815,708455180,356871292,806957151,169606052,651094973,169524677,637930417,103647626,396412465,10026261,800622739,726820849,791025007,833517719,689452430,598210376,750837825,510393581,928208327,869118659,886513497,390801193,190658225,140164829,753698822,557551348,87332553,505360879,302469468,510556227,721337424,765876431,861174277,863776406,293580500,83021272,621631601,47353930,101530698,762899077,567414549,354427294,887377127,666423652,455100059,322919577,618154670,947138151,47607224,270697084,28505020,780975015,220005219,453854177,65238695,250086895,377925664,332985600,146595118,660405117,233313723,791581617,451043754,75099568,625538587,140074575,591304913,654838122,803604157,650410716,761140582,77160142,336340962,498568008,744298440,331637305,108121170,214317406,495545201,479588719,734451620,985352962,580830317,347457135,704031752,26760894,946263235,729784610,3810831,210084363,217751851,236203847,121255451,564341110,238745549,96989447,954526234,19571748,170349223,256668088,318886771,558260932,128408959,741287256,262275345,70774702,951959723,626872889,90851819,878627494,994734886,349037107,488817392,74452500,487684946,368785401,538429365,33732744,596502756,761134474,619997917,714335775,407783695,793222866,911206864,947876491,926490791,126799940,822813756,383594059,112419897,448578097,584475309,479295563,102346022,788169085,78676899,265693519,892471720,746407392,62550148,160834053,248995776,573862876,357276833,180433797,96895193,517882903,99708008,548224374,95186766,514616303,32536630,820767581,353269186,395903725,49567669,653136425,474975158,503743185,824152399,52825421,719083114,384910260,965995056,502534872,50410053,133203853,872175775,727854581,985089555,448716162,402945048,281482745,766999452,762940470,908601631,111398400,814652263,297829547,984298919,838377370,761228201,47783959,93598582,591811579,580438996,212976029,780363501,679707656,26550930,712365581,299966420,36996362,175082151,346094045,62393170,669988454,239185157,688525093,399348015,748669808,579753861,582813966,474391173,278641878,619693086,678987030,6913052,223548026,222774379,897969710,454823432,323121951,517465772,885943301,190430187,809518879,274895608,726137537,836997036,391296202,713318478,135437123,106544088,271082574,64984509,711423596,854915123,538368762,15178123,341137846,869923879,534944155,85361674,154578722,696851431,399168657,88704971,510796579,465966194,413940527,398904656,739586036,587158216,680778347,48806813,104836584,490350257,422015860,475051557,994802600,132601236,688431513,619527533,398526475,825948910,389036162,590553266,552303806,145745108,52167507,605962173,38787537,7567896,78050055,260723224,901564466,742345408,866766833,14079561,411980557,669943571,484836576,95376114,756525914,473341289,167615735,412091859,393112638,384408694,919088460,62852927,600168343,298650842,755418455,394652121,488695711,176843580,92681612,774208809,524035690,637405483,225521545,824948438,753972434,861180938,621222764,972986481,688792840,604404550,422600118,704741175,5593598,108278274,707280687,737498842,660405588,241229820,693437782,215049805,127094734,482449220,418768046,930637903,107834620,693238850,166566975,112935362,315042342,14947070,107302438,131769142,381308115,347264735,410827177,612438734,368682267,952539874,994557580,309517390,853380696,873563006,420725881,623716043,720832272,865721355,770083638,704741975,226060620,295247375,180901986,730318197,234389305,896040537,597972595,694914783,416685495,81920176,88358883,929525082,377499827,972899151,575542599,878115305,976308951,49476377,59254006,35623790,374079595,471118396,107653661,946828231,281232725,859880606,595884379,105490470,742794024,816721357,67859122,780404053,213781473,285075280,224214503,686835083,705615934,675282582,816259857,753879563,300298041,522604637,208017829,52274687,259852786,511519951,531756094,190711622,244629630,999469630,261963154,266231506,137463219,237874717,138796483,585249139,807175913,551371692,512090639,740396144,110720068,589818083,288006429,95911865,377979805,242933387,408000940,149492287,753979197,974846679,888369568,166510363,368478900,829517999,38151447,54221501,206174488,283497205,264290320,931226244,258663572,851753076,287957430,419869319,905358969,446552988,553701629,16636152,223911132,676024558,401748607,500251681,331524562,360733216,289804409,42769245,208657548,66613685,737223708,685700813,969292867,887248105,999939614,571049654,527116335,874198470,718056163,304813979,260046958,272980039,743424059,461279945,109048523,767953748,414902744,183995177,823466737,620827491,417579042,274400498,201779777,229012004,507034382,304725556,566900175,653783133,252273210,823121292,109900670,264624270,101472953,353905353,705049328,742270128,601535873,807891082,479293771,279249300,91216405,563773455,642607621,611025384,236828934,96695847,314958328,104912488,766068785,946584308,476586158,662532774,485622923,426608261,350123872,426723924,501093335,237796389,176842856,80513344,273074998,398937747,502767895,819343967,841887383,624474576,791615943,27960836,431830537,428592146,481024362,93499757,639869942,488989596,28222903,895928381,505945281,534579294,395593788,135423804,882691655,374590687,116601983,224442217,12035565,4235293,901566256,772429938,691321851,159819487,377054190,73012680,349423832,546053526,116966429,345708707,382973414,418657617,15119925,155982638,670147526,410719545,950951357,66156125,282442307,68993879,731933551,820861641,786651959,350143981,557674465,9076325,660412494,2793893,859803064,85614563,902895429,844025501,407106872,155276940,339878053,816914329,16172232,16742280,653099359,644985474,566390040,669878776,188805589,422187704,215750018,951134968,650117486,127791266,304160662,17166374,545417698,20539821,615388027,338304415,138584227,312829841,484148409,59750158,139020935,648603765,249464761,659137761,53192832,658730272,1481219,65506194,889448803,332365254,457858131,787700516,793372304,275327683,398087474,244615113,755482411,115055544,3245708,656501759,847063805,932274672,699723792,637321172,955990215,647875229,96883513,321577143,323681480,538556509,23158305,113049184,80565049,935059511,52851209,5018383,592100848,147215785,940494307,53670760,101331580,125332989,937572063,331639733,148928566,16938585,657430200,626007585,787094442,197021174,62571391,956338663,416294893,959523303,253448198,36770363,110157761,83563991,798670177,476871089,156400797,901189829,95293712,726100569,215675860,59266531,246131465,471006711,378047513,233418096,752800050,129770804,362001123,124680888,360623722,804043820,597375816,402268365,438868377,247463372,588552612,287050380,444076,459607900,131297041,243662618,779284475,78891919,377545943,747970763,568322781,941202058,211423582,103685467,32406152,129812551,502116461,253605895,746721617,48762429,4369627,425876991,151592286,895945460,13456,226154992,88379001,913143239,280276411,966980384,676051970,69483513,725782670,315198308,488783985,867486120,572739357,8667245,434477297,815530879,386848199,117659702,260129783,517536167,921588419,484495969,458740137,579189829,47567799,46554618,759417218,29868805,286810815,476063837,473818315,595057129,293823024,218659915,465649966,541547472,545644496,684850160,557269778,856974279,141370371,333385324,422305445,254160780,335255577,790876558,131513954,594352115,329554608,256949621,755644608,48121945,770151852,58236095,314484211,578879010,118600160,241043282,853260910,653298282,47822110,25792301,846989860,482459635,948318020,550312684,40696006,516446605,936672708,248565777,789320624,105240049,35956993,886276544,703299416,603291624,252027081,774377061,997341985,9855638,873424203,235347507,968156022,107647013,835095295,286484851,292554183,368085698,308917857,514447800,347990356,868921089,860921801,560874499,311978010,52326674,133598295,59111528,788479691,4064647,181002581,66513293,635892520,566956168,240352415,979277476,401868524,368213053,656394764,196282487,177855795,718088519,55642693,31354806,639709505,87492231,41585378,786241349,684451230,294904209,62783387,785914632,842790974,778742984,567987270,390214553,713912911,743159388,514943164,290659938,743764688,743780607,218352662,951121158,418012816,122389175,498508977,106669492,438285377,393422029,141892290,76869860,107043751,78984027,132626521,758891439,783035740,701893364,594095777,316249136,970181005,136303011,65611684,869440655,3332975,768693159,957281539,83342649,580563899,519242172,322621974,58791990,860455466,313116742,11126222,753293021,972683460,38369834,75179447,820581293,369810417,586004101,610920365,619258248,167620774,496782332,4234388,300398765,67989258,234159002,320305310,422820719,324436310,340082437,311533992,179650736,820890848,277534008,972569750,481750933,567560319,656900037,305492632,928749694,230455593,354136010,79712811,289375905,283353458,350323207,274958553,991075574,916984664,64091907,303373802,470290814,83384869,290155439,500079514,732881087,359208595,642324448,146704067,344027313,41071867,745596560,467282253,58107670,303528883,136274956,948596368,933540226,495053400,10845322,534195437,741065199,470625571,621699896,402209417,448129341,484684158,681170435,196178888,791172471,16977873,879270107,850691920,425956292,484404193,63744552,553324189,115453013,34034828,231177603,604056198,217320417,427543550,244161988,936766546,825701043,311081365,14799688,777736811,482601766,42146443,833147638,911952004,379521167,378800757,8288122,859513046,506249331,202296703,534074120,849574027,964881464,113746951,277538205,43108729,619397842,11788416,559412188,357237150,867986685,188779302,773360673,94778045,87693397,482120115,329951252,480894388,56510386,582285528,389889717,903866622,134480723,503188326,295593196,905169661,412337079,219557884,732450842,925036890,460889597,990920628,667312311,358406343,836755544,627507452,18533925,907527238,381428072,215898387,149805457,929481515,999774327,295059761,322640782,20392977,87843144,496929228,325631813,105548535,925713901,101995239,127988723,913810323,754538964,438410991,150111458,422967959,651615343,679953748,15135527,418205452,65055133,312444008,648925541,569608121,714569899,47738469,122026730,642325381,955363576,60393213,416449507,410637154,359184398,235645469,533552415,671212680,132893647,953510827,133495475,331015788,399703186,275577864,307912247,793029706,959734038,293282627,519120702,428559331,136524079,47660757,815921146,503614727,812642440,878472738,541234441,934004842,506898502,375495465,645325369,984038011,748263908,200243502,178641843,44295373,88487080,143669836,680293002,274526564,966065970,339881401,80205587,543054040,96729108,873975955,125730205,23646787,147074414,125998401,236249665,98339999,823912159,517100457,41061390,776531043,899116882,762495482,19622903,675606239,168017184,716794261,925368604,386534432,139145027,793755784,485046524,329004856,961707414,100074707,475904948,305359608,485993904,219234987,393466835,894946732,394261136,359861757,675578525,495206564,83083954,527644328,158242233,785433623,993902230,386973244,71807370,566615132,951011304,719180285,225084679,72476164,69617655,271297126,375992679,57561410,66976720,189280590,608573501,623199224,831611349,68367967,949648802,648950710,992623504,15756763,683427160,617733964,111761928,920489927,202010101,12121600,864268382,972286544,16874985,943010069,740914823,445244855,42746768,185391678,672138927,874962869,680408274,64419421,158429237,633442557,192617320,854419789,803224812,717210242,326826683,860375802,121687541,236543152,588525067,31122987,245516288,869145107,331025033,200578832,726587281,953393503,102093232,627473427,446675750,823983985,369774970,137730019,427015023,744121865,658908574,496214217,193343818,179769793,674398200,191858534,193426791,426813357,856710119,996600545,285891793,62446612,213683079,778850969,235407518,622255830,801352498,461483549,236053657,951517190,986176768,187130808,984409426,548184872,431276652,502360117,53764993,685105611,555667441,843783731,284140707,696715268,258160763,990976801,611411922,83900737,15909258,98926978,306355046,36451194,602378163,931873583,401071910,11907084,992338773,672733787,928335232,61548769,156021307,172573762,344294484,29426148,82504135,520044630,924631698,93278594,863245626,169717050,576176134,788519815,530945068,799204591,868832599,373670371,35741569,206107601,159327396,50920410,559312873,835533592,417513011,312101128,121570900,423641512,234602379,975186539,364967069,788232851,2908414,637073864,739946884,209479611,998124644,486124991,67909127,473354441,388661399,379857397,941872495,742040006,821821291,528598911,22049538,219397882,983759453,568528318,100695123,958797003,931425980,113637808,797676873,962279937,132534180,354399899,72444293,95488249,139190143,759041818,162971946,820825075,965065775,63978281,979618776,843130330,39848335,863552128,819107448,14196197,224798162,758973661,17457247,346174337,411860814,597885195,373466630,551928807,285587856,42123325,90098343,306879666,618310015,56032850,939251142,634633075,874300523,78755865,238370012,227790029,296653380,543812973,967214157,664612556,873759223,571061353,516720006,882250952,764651376,746511362,809973938,126116211,861777266,260794294,948554309,581159682,588127396,582896009,60309296,592013644,474556735,913758765,888003658,813617003,78083903,243649404,911701846,470082955,884865950,617766175,860153627,535075963,507680152,420763711,905019784,40837987,316764116,35515277,697785251,268517290,106950683,869295220,913511999,35574790,698020242,716022311,836106836,107585262,4267660,859601269,196034714,308502278,765241066,920012957,775509899,916618850,712812019,213315298,40006643,22245968,18808176,221896501,28376046,174835488,702417720,817012481,518329249,366015711,25868347,416084844,931218476,128106796,312306078,271198256,861768236,902005662,715075639,750754639,112286479,708210487,184778266,306963100,873101606,462932091,166400356,667074898,663173346,307276870,497161633,84179001,190703590,902614384,208448058,633661127,364134594,474705986,481758097,894987089,72541235,222803727,598242968,944106500,988761464,678443540,255389788,663840210,777841883,101063223,57507831,752431623,380069156,205938714,261305812,162724169,158425752,574870162,313884881,243357935,100928235,374721671,170566424,966703070,310202866,636757593,866831128,94685626,888912333,53332199,292061303,674186126,715476688,48734241,323592489,190368419,564362681,955794415,652031923,884457798,200406452,976880268,914182961,575014889,391806501,699979183,427688993,334117420,634719613,181261042,115500026,469677250,508632956,609176432,19242306,282889892,794598964,771470902,398167906,448952090,427724719,934564302,319808134,656718275,545585992,701573432,659449594,999202769,278819043,302337947,447566427,761206795,835496964,594884793,692339166,870942094,468214484,693728558,600133321,503014666,671856870,222376742,657335592,976393154,110171129,101218545,958994547,749559272,496589780,855958796,899511697,955700246,69333540,352670106,64584400,783747643,574923781,215059414,81571775,675234217,3389302,129423892,619397011,352326868,738234275,135926137,735467798,884387432,165248737,432145766,77173586,769315692,37280504,94162960,694399459,345569615,985716395,39576385,26329281,927573063,136676268,103512564,273909078,532418425,585090504,288481115,631508526,692591586,818397740,971035723,469162908,454021550,730793059,979965420,226725097,725694079,973733018,350938317,230199157,132162030,187620721,835464051,396221071,733729528,941076022,447641599,877138952,746613256,375022749,935817076,107365704,609123648,486606687,780860633,652092014,101428657,402401059,728594210,531132276,798125800,710440016,149250170,979686072,826690555,116445442,179414786,357267914,237553586,391020129,575348283,907213587,197841587,611845731,932477659,609337585,934762199,350895719,514254571,602379269,743440703,741015653,785389596,253940441,926985298,995528148,589468237,643574226,469865021,724037928,263111994,247432563,863724327,418288747,464994198,257472931,960981190,133834890,386091330,488885723,222891617,720905129,942745307,586027183,998859539,952603374,914318433,704409146,720149489,334627131,966002871,426860155,288739036,671419479,313597146,702363084,46228876,165595874,824026384,289396385,982065887,815030545,567669249,340202900,188671986,117184308,860117413,73910912,413623527,366052950,858765642,829532185,483596971,736171349,971550854,182529968,174524260,559554596,603204759,939570673,710023298,587921685,627499948,99435619,472171167,828728104,1793133,658372429,75159790,490206094,146551966,728128031,285996411,466256269,994263758,20723399,198794757,451904745,660873423,307176655,960331775,956535220,217839676,564794975,631425085,644703768,126724592,703923567,148957824,361194144,801191786,700859190,185581113,708489325,576241238,882722743,897086703,646510312,779043611,971152896,291005872,908405063,895625896,864530827,88232365,950620703,596800219,672649243,654887871,639735600,378587249,69331529,757344738,557435797,499771965,651850916,137240443,788645779,293516947,162369648,287937177,79477148,830576580,856874560,465393138,727027992,124993761,117091517,300579076,950992588,759125542,215616145,848615104,28131779,950364469,585242675,698535465,139945753,12150715,206120540,376793169,981000027,80990701,853563156,438179510,554577585,499421693,59796706,128374593,956676472,651399815,205058299,851061505,195120446,181806953,907713037,2163149,641801822,100347120,197856454,68736822,706543846,445335459,565528196,862747128,381395752,27201216,342777657,158434876,82722299,330233193,131530903,672192536,421464263,148800435,10924515,510687119,773755621,142734493,199390152,75795344,227522515,95512876,114622623,962571980,952955009,381796937,179982923,316011885,277670742,123174441,811572757,434684802,801078698,154694243,136424162,515839385,114039334,896651992,930257123,943494679,88799083,738031894,236497386,966819552,120432193,174272277,619443609,135499454,445131067,632300568,119539598,643287150,294451052,829486854,514697432,455609508,649799401,17166190,187820141,39632344,966832194,332906287,961065174,397870331,535554937,967861582,808466296,556980881,89428272,575393182,514347433,15627256,447265236,787035530,147349415,38930070,901131311,259265333,21110546,263123445,439889520,229944597,355760826,470707912,651100014,608753833,506555501,846107177,679591983,584423535,609129945,592440366,411043870,752409269,358870547,48697584,269024781,46417332,392513641,699979281,636357501,791957247,321806223,233366815,683898861,748656661,358792232,879941026,596430740,550761562,995053964,416813759,90169577,149604435,845872055,22863823,665678926,823392059,158692923,770245865,490828939,877289646,131843667,279344721,340452083,874701951,235621673,133613043,514002586,307729599,870748417,715073861,720871793,382467155,706918614,301610294,895782916,208598673,224585207,120301201,120173380,912348058,593549804,522994091,104098844,183077381,784959963,623033198,981674592,35491490,90975720,813547954,272082429,896699740,939779181,919449960,50637555,100336182,575547979,968536965,274726495,238360415,66493250,653534888,374986789,685942425,735098457,119324186,524846382,377804045,436418714,232671693,738401642,8401081,610531312,315873996,107653966,951954366,536837790,846914061,355989489,18879659,275827635,565351219,35778336,31071992,388443323,216642781,130438602,493758805,727423627,184496618,15756105,110841663,47508092,397564138,38841549,767863933,259887108,733864736,66033231,364446496,628897028,105322709,70718544,8112217,843539936,481645436,148977309,688678539,830831290,635796814,751404004,643250868,477638056,161913284,207762017,840788275,686140665,126455912,921659610,533519459,117321188,220197348,535482633,545626832,594992734,359019906,411490650,26011210,24204707,372574775,949412420,764024308,944797721,514189507,301827199,246337957,646550461,306344207,208785190,857387710,499970600,49847136,848149578,646487238,391238893,750126115,640606915,137876572,742647647,297025343,145922751,683308339,413687995,449566626,811791614,611025685,34866419,529847080,672673098,55818856,283116209,303341489,134227645,106200165,140241076,35182151,186882441,312093973,1316815,95346744,469925746,744643003,473235283,533456540,852820133,42115253,101915886,794302852,89683812,575286668,871650282,840333387,276267568,369370562,783295704,569119596,93864812,125876964,928698809,522715045,709140016,129491709,404692261,582120578,912542361,564233031,924250512,922115011,390488056,222731960,392054999,788539197,856698342,798664506,27053523,569511544,238883907,67867284,917582787,526810580,823320057,303060378,497540940,16740809,628376262,588238066,649948121,221735936,831748807,231140926,780604437,641173136,123956106,271135952,21646330,885131967,793746600,330691036,236563616,932463515,726124446,616976599,474651677,361965312,877310480,127495636,423453124,215848910,672750587,417714254,399424935,101002023,28919431,510551173,281889777,372556757,646583894,661231216,878152665,604218471,442654012,802626476,398395325,769194507,524209,220446075,627891450,236958792,131735606,817668563,807681188,453594029,135382200,621926736,919742003,516553315,582664031,101917275,24669197,150850108,307061696,175699509,984611716,7610677,649586675,943869024,937964557,840340519,396135092,643185544,734242657,768279115,440894972,303212254,902637225,799358167,155017137,475357748,698503796,607684870,720363536,784631413,396060642,539388041,759309678,15422603,509650981,184748362,951850219,933922808,275636711,296953776,943096182,40732367,689092423,990023668,624491120,69670951,374064420,9050749,230556662,698297624,83014291,149796865,785075771,628956029,949468869,919784073,16602383,449334127,51664568,743000988,198011,180487230,994943624,355307957,656294639,660965259,703180660,754843179,463406624,344920477,20093686,352626601,333395865,599468032,413425747,129910362,998542291,63067179,699112991,109007000,70076687,750818431,184438623,834012718,418966035,756250310,490737224,128814219,317062557,963467292,968078264,155273376,279977905,244957336,64773431,665824366,120318492,849256726,281475920,652291677,162197404,895020985,642231307,521745505,593950412,813561806,297871571,336091218,596087894,230999781,555864069,853543233,310355071,47383381,242008586,897256062,552464800,704087619,758696141,441124479,865569109,565790185,178050379,47999582,68101980,128677656,755289019,159683494,238903486,603952959,275161122,100685463,796441383,524752330,944555728,741980450,820863599,819560065,385900597,430719839,88443683,253613,553463553,103238692,551866824,36818153,120385713,186061495,192335011,404619720,155902569,324427843,197777568,890383467,801856151,129423510,405955315,128411264,780027391,680179249,510163540,209392887,688038023,448592044,818882538,529101121,20242067,344477352,14942752,34729812,174355456,17433062,378170551,508339184,759696300,70927616,227018027,561022717,301089220,935048208,69903110,188014861,17324090,48666863,338654090,720604658,187696504,109148932,101022742,815617173,689707810,949919811,701810257,137778653,96923014,192491872,893498900,475847407,338268021,881415338,605388760,138853481,981688034,113927537,372184882,484426641,648049510,878540633,327840637,722031504,546377109,319996391,880291449,43539160,263717071,34048536,461567959,861753949,868905475,805518725,616300387,846974828,584321880,48098007,722330955,284282772,582413007,384945623,560340997,728323062,61893712,658511014,256874238,843187596,209339419,789401347,314467863,304118174,303070558,23141269,826725132,343076012,877920067,989911179,674350722,186874366,176377448,641314254,141221263,329315884,539682647,268301779,779824600,212333137,358190823,716499620,268304611,472916955,478285138,507023645,331290219,717097709,375946777,433570143,394357708,628442292,698004276,447681749,551940002,119237152,416571013,512326271,405695874,62953671,145889104,679329701,116712186,929140391,708954200,946944422,86571215,948960064,603727957,143024871,223279413,3162982,266125877,716661685,490142350,75206558,276235870,629600854,49624409,606765605,302662210,602487374,412877791,510348458,169826066,53902977,502213983,99679571,70283715,935370733,195613491,671458258,172377221,188513544,808754683,315955318,326949173,771581585,110933440,442520484,705905027,446122761,912811028,784752006,629888615,236551173,723334014,169847631,623367354,509888612,31128932,783907412,319699139,179344379,321421112,996235757,597350818,189148401,741378047,640716035,31394187,154102325,132497993,100710059,2804933,483825853,81002407,488779407,583522252,493652093,81398690,913678269,682591033,242827935,783152823,315202276,555474161,742810418,92255315,844864649,478281779,450568932,684700802,548998588,75015935,219918756,355175605,579338222,39620234,970320846,191643404,872704175,18738793,55776420,131420848,969981798,728693187,840133646,421209297,158554167,585657420,226703739,366730173,148929299,29258116,553357605,322570656,196290364,310244534,982566600,995084417,574132261,796884656,532390700,119116429,535063199,293155604,531728788,879263327,736740460,799181196,475632834,819885482,205711753,96244648,114569901,869451904,399416340,749524436,118122550,10808022,54777984,969049681,302009719,373489372,934153601,66628790,991093443,424330369,720298674,694495779,816936208,383892585,834779085,414394322,228881211,456280078,828146087,809768002,166938575,915965621,116905382,28701916,795238793,787658670,883045160,873498281,687397875,781547912,111266863,751393551,113062228,861322048,845374887,463917257,691699789,862351090,960614605,267608089,858395005,249708489,667528385,694994767,613492936,906786105,810107623,225476359,65507336,470168888,181658234,555676451,640709732,925459666,124034888,33698535,228573515,934305769,269611297,959552087,737220886,283766390,848020390,622708169,168384552,448697296,440369255,850399801,958763200,8793890,770021234,803401594,186396600,736498874,33812588,145462286,386724025,385172353,869003391,96687868,180855275,945246420,820044081,723801499,584417085,500724795,840700619,5884851,122442995,610083139,580386395,476394669,739144445,400767798,195663994,520262179,286010447,909180743,254599196,54240926,532650463,544490945,624471326,529971771,266366019,457760985,95429919,306321480,619791079,178471734,687262126,292993047,154138358,738104624,458870496,415628473,496420598,367021991,965568553,924233539,636849800,269070530,460815706,103539660,522290128,10010938,750110500,378165610,70790728,73825058,679685487,801440194,580885152,269068980,434764856,353567698,118027615,208214055,202761422,547650343,244403759,705244449,874185128,139312100,661289470,64249065,442739592,93485889,406790466,132408592,598147452,693274157,759971724,405011490,652435087,217984205,846410231,685074689,390466456,652679338,235164890,46395750,29784967,25229196,765797291,678551944,77335816,141410233,3345958,193919862,123923066,863316319,3349232,455967402,222472918,126281977,500322781,171997193,243833889,717373947,930732971,558158849,767205047,923408341,7153965,563562679,40557614,899502399,799428760,134452266,24911527,76206771,345420094,827222017,311309041,900887995,464820615,487547097,553945974,621353851,674176974,768680446,98119217,408196379,139268266,72055079,434893001,5311997,231904052,721561237,439555650,268063870,76255331,161568014,847260068,728878197,9134491,845029878,900780513,451349219,914082529,34537912,96575803,799367536,105460498,593559689,689131286,643194109,523689543,262163795,343437499,865486204,112868075,184149733,480627204,215421261,720683363,717512861,117976922,503700451,105922061,761114442,637825162,482110488,375171685,498522203,328958874,981866518,759203056,370910296,891801278,8685511,534452537,412672536,562616389,316130760,128119220,166611177,62859798,508627818,168316997,667805480,57163138,608648735,887657062,76323903,521079040,130091392,100651276,221860474,777375326,56595734,16729364,436020147,769385643,858441892,830716876,860324363,257152268,14049090,485811616,95982796,215612053,779840860,485614957,85702277,22599558,519144365,33284794,71784538,389899130,62070913,341760927,604628011,883341851,772038046,547243948,4057582,62261126,391187171,28318108,787028678,239209273,93842705,754324615,130814642,164390722,43873190,228286918,412437284,549198250,490272944,122616269,374815610,749399197,953692902,46146353,926115460,54041342,680230891,585132056,779824157,204887636,923190689,289539026,877444458,438801657,480605401,848978240,895929012,871055567,227871548,666743213,176489423,375794432,20591375,127351036,140644571,581293097,682949654,827720141,93344521,178302137,777307572,858316481,870417846,247112936,786720632,356847445,760665691,331096624,403808769,558634641,966885181,430480218,208617183,535682777,761963393,666737668,83294608,566117390,382417520,665681747,870804606,304937315,978450041,173048939,740659735,452948133,662721294,506594916,361071435,886305270,979075876,101523196,636812963,4456140,318374491,183800491,53367851,98285889,476011880,955082085,771824917,53130717,200720623,607679902,991371429,446968708,305278150,471434367,330232386,910946232,655380339,326710688,703826415,870629229,859364792,162028000,195331604,583255812,310562307,235431539,25976777,90984207,163210385,740323476,96410414,167158260,313244122,4518235,214521509,985442097,724417193,987946486,866010176,536352313,129953063,130260842,8135201,82348377,49703571,789757692,8590984,93220895,686477111,338652893,700486679,367239677,122228439,91986319,411794749,487530740,279033875,411030655,884809833,467586334,80851165,301360182,194139248,663659921,895208307,495584867,353276603,520561244,224450030,350370078,62719450,504304051,867714095,902326466,18882595,118151565,143958058,436494284,148271614,712964556,629521010,855169948,526245243,266140755,612211162,838846957,270663744,675181062,464518286,55775957,916617785,340407495,332332857,60845399,12362177,51152236,515150230,268829484,59027947,531217471,875493096,647493806,128758093,166731453,936854883,162897355,567174138,963311980,298211705,610272415,466580833,361265034,638134947,393699689,306535194,916714983,181035703,475711100,194839919,909440605,120111114,658821974,188211664,823003395,275889438,456590593,959025820,482186005,289880835,534282449,848970814,564098808,461343129,378003433,640049183,354009436,99867240,722447882,309012636,959914806,390988178,831326404,574264646,874395704,738000707,859821124,389148983,132230744,342496919,882522251,674901306,57626488,13259019,653516692,69166617,694678892,747032752,983041080,25230120,988348381,385229922,43586996,860675301,712916293,172869838,670971453,580580174,792776097,992294869,934839259,853064561,855249355,67860114,4098019,948907207,69865427,347655258,886401366,446677701,502269373,30619301,808473783,889836312,402778076,622667988,493062485,909275269,488792609,805408266,700278199,10799964,126368600,808711895,596817402,961443924,114049218,708267311,346840656,80287434,564151500,346937573,354666384,256290394,767939723,179184569,575956667,40400171,400841545,287646176,483590635,629682197,62251141,223369276,158985354,390166388,51887403,779178695,94026037,540618245,167533258,380405989,424640004,836388247,896797714,84439483,835183761,773332913,628215725,37576354,185589460,55798776,152653071,544689779,671307070,926327799,327855621,973867592,465239888,298838889,768440737,9792279,15570912,854796697,695466627,101593015,810260896,654052023,476540146,243714159,645534062,196573968,781809668,215632661,333220938,599932168,624224911,890463582,207886731,143877895,675151899,767354323,284806426,793531197,5380109,22157367,677174816,406781990,344457529,474756169,325183778,810853809,88744001,166773789,293890966,6056040,645111449,536168218,537857114,5844775,241864241,973238363,627206320,606880764,90655876,87402209,883090693,845792834,45901545,313616120,814237680,919867654,273864603,577905678,585173343,680756188,469359078,810588515,72398684,767411295,94851183,730966607,749303009,484544833,279997385,572357696,829520337,77446213,56390387,505924560,979300025,573828145,773552916,237860274,250558051,706709968,89864266,106188330,148351653,117717804,650692941,209528863,471397939,717986990,496728437,245904770,955911140,466345351,343981285,267479271,840834526,463481222,598689063,999174224,592041806,154896891,394845451,236004305,915036704,891487961,244755408,172958251,9445097,977439048,361158764,206560126,115442708,506333624,619009154,69043788,216249045,955368591,144680318,690616222,37731119,639241168,13108282,706037089,518205148,73228782,248009343,27268974,895629207,127200226,900948195,122096946,29467115,771036504,894196730,673879404,62388750,595701514,386583484,170583413,897732124,111187893,10101917,717668062,224451413,373614159,883965063,508943895,392677264,509528817,633526730,252807862,12061446,291733613,461667590,388768519,387244659,191028334,125157273,131796898,847803207,267480782,659208481,241783872,415455158,878482687,501425862,531610384,36730946,447676242,459383853,453684984,162074169,971293987,514838662,474757049,132952516,588417041,363013652,169408037,825045584,32200187,815642443,114420700,863819413,16399149,181063936,157244553,404316461,501479497,285570182,99581476,214579628,814764483,390932509,43181168,482375046,319609275,609462356,529799680,876021298,142071654,943956961,268438069,922966983,824679578,323188286,632358117,939281994,360184061,4595981,521198531,990892982,202665989,298212981,986223216,967782344,269691808,165216817,102687748,443612095,518236859,960700628,358891581,756721091,606197481,491620377,87064808,300337958,193489656,483385412,120961461,125239896,372958012,948025738,80380051,766260350,871249969,554723737,808314710,156758626,472770891,170871137,645563520,898695996,131115421,131637503,316335089,267309429,133783679,86914544,483861048,879546194,48435188,153902503,69056933,791682129,785843869,653477233,760484273,783993014,403906884,267191221,294545470,475907955,355898257,633027082,445158514,739097228,961696748,275316314,207008691,271561497,731330204,417826847,937270417,911347774,168667214,904430236,869722986,660524220,880572775,122312879,570707174,213505916,741734653,191742136,384609252,994899472,967750362,86675403,198059064,179035798,430067539,862655818,787210807,798262660,70183811,403767852,870942622,684110002,209357576,94566046,26614920,433340442,828740295,852182201,57810364,749157882,192878991,957356992,144459798,717777385,268864496,292969562,552404541,691314606,38052772,395790776,298717473,520780603,763733096,345364931,693076054,577938250,339632369,189692057,288669851,301605762,819613592,78507464,358461699,974145258,44026478,218641178,150737207,202513167,24700921,122508885,717496369,633774456,121371450,573474078,472221210,669800805,25830639,136831557,565971140,71877417,950916483,273007385,55544634,530760840,643346820,149841095,528449381,449361053,858714919,124514371,502434728,514773492,733949928,143350106,601558186,35422026,485020763,43523376,791413961,928216656,9104162,128268953,328668639,398854167,38501060,133211182,202375700,507271630,204206820,425155834,916008469,44073140,2889412,756180759,321793567,20657423,89936125,875449034,54427419,519554667,279758145,846418310,613837020,40333530,73784836,3674333,270467546,672648570,643576760,512453959,404264443,627212971,718664121,932829497,80227910,918236701,779724943,684881585,85429753,91761053,920716381,506033763,874212621,955892020,144995511,338592610,41815367,2194109,369167964,525714765,940331597,820992506,838616367,690104908,34011309,397420261,768184457,204483035,772534045,293564553,169505112,102080040,405755483,64802134,941214265,416586631,567796575,332687335,576106204,406184883,46298415,186854200,837447486,372074764,135662131,31759759,3303635,275575779,272869652,242654819,21075858,680122229,906333469,438083890,94975892,117940632,100795843,858619465,520218993,914688414,480228872,756084856,650414071,610506645,901295727,875121398,842816461,414124415,194542978,213720512,53482331,229372671,126313710,33659312,362331132,583196279,457474823,580872479,56073869,481173828,812596241,102006145,725328709,482431791,125838843,849525653,151859646,94497686,25172047,598272626,442568506,158505712,125779304,641832258,257379903,544943241,636275610,563098857,835035848,641864191,1099256,88304994,816791237,887827213,788568113,135668132,132618566,625191754,107808354,44764766,535124290,965406972,356025319,621074469,273570994,145207931,968273325,138696309,49108368,523599106,535167714,902255562,827199067,73072038,347053738,159567892,443464319,536554343,377987626,374380934,886250606,267359450,974486626,486431160,771240569,28949891,229513815,351037271,538813966,700765741,969488839,240487284,98537112,196328125,944893661,979169440,733591119,762319606,418180040,785439296,89248341,846260159,103276810,399537472,637906313,53036767,976208042,353498814,314799296,225040242,532644927,451447393,209587878,463263044,79255064,599999508,756008291,363586116,200875897,69886373,699694680,148035788,251425690,256733112,618766561,493771953,741380641,477291971,787713630,659274233,553899158,834517339,517218016,16875503,744694673,341652973,583223711,125545869,13457507,133010723,128228581,650136435,446267109,398405639,942541905,462417063,893237926,739129752,153822547,872720088,286188584,401140586,18660969,895272099,567737011,479078834,754749013,673737240,968005696,728601578,654966252,16622842,207231384,866879101,900967837,452220040,310564125,58965243,477351343,992600256,772511274,703830934,946580062,612245058,408537029,569605522,670888506,333973592,364886064,574265463,681105601,46976075,838867585,617358540,451483123,810101988,130768914,750345295,822376459,269372899,247764195,995012410,718415681,259287133,387503146,240452049,860847536,460186291,55358568,136990381,880821039,147402280,779948478,353888458,421095063,31601907,704790140,35569775,259228068,749302760,480359890,810620735,259415155,391685253,809647694,85384244,119869868,899167746,262861661,335053126,328744826,531845429,899186389,783215984,583770625,373089810,15671077,829259714,199144168,236509550,816754831,482972993,986391338,498441504,120134428,50660372,483821501,214879765,209694679,317805226,560603293,48786062,401569458,784261732,625283016,494165141,907240416,648756590,670510889,75310545,876461732,101994951,330169729,857870033,16438673,406870295,474094595,736506373,159848281,860994948,997277550,133918015,197216049,42868222,872163987,529733665,913990840,286499467,331183873,722719065,571818023,556192236,74078708,86287252,471361217,893778914,94096833,937508039,610093434,753414460,866225086,646355967,125429421,849294549,917167081,982490779,720760870,20173010,331320000,863121907,237855464,169716381,357910829,98586334,23602279,984985614,849263422,39510523,480913138,726146705,991083612,259100752,402481326,77641679,839598733,20861094,572572397,350054172,402759671,106313731,901461191,361107552,345840042,442837112,377999460,780296394,906345376,638204839,420890886,101987784,416735382,127392407,835966968,258812502,314517,429593434,336824024,234477876,237169687,381280577,91454991,633226132,495624570,20564924,475767657,938371996,891211782,45465896,227092896,464840931,828998109,97316227,358771822,536910156,122707198,755575666,889413751,890729937,182526500,909216162,495381260,78737401,489572055,227676728,539887120,764417265,313796501,550933853,743265154,938047257,82795772,772115326,846088908,372544900,447303295,279209496,422230577,143337951,397269101,375121984,810681143,127208764,251467783,964190163,232469279,838418260,655487853,986214839,34011527,194062765,378210140,26227860,577495385,486334902,300916010,964369963,106884232,899936910,305299127,616973384,66112103,897069622,713935014,907623087,637857146,19665576,599832772,101159986,181814856,40538758,21063116,820472504,481855919,184576374,1710128,263307394,591058138,447752922,600660966,135714662,914648276,598608084,638160171,24660879,804028060,332497496,325944356,708986373,694697455,704516024,723469457,91733063,657309873,751155343,758972735,794872543,74545861,347793135,56216458,523162082,780039934,536484381,556641361,825566573,198527722,258814794,245857583,162839231,737767717,884420419,719661246,511640196,405230162,825666675,733458389,679010143,395373243,723691283,879500420,426595217,130893364,901514220,252365955,27381438,431306586,5460855,24750320,159779300,56136350,531291995,980534317,50758741,551152128,116845785,820033715,549580137,466196812,349475028,51999629,724898852,700276133,330581771,340608986,216803378,682108734,726763230,615601052,978153365,629266348,515527939,529038775,765371423,963439409,499448683,867922705,113467442,81819158,745054426,152592125,520370357,311179515,664406738,562059744,905037902,138325791,57241861,577241127,153482921,459593200,31717788,90875616,71562251,741867393,68198247,244648409,522109705,272608871,947654424,134672947,456291,226431896,92832166,950064818,991459259,923127518,227824029,75112802,847962425,795974061,53384642,173470804,33988780,18775358,24829444,135111299,925387414,909695524,316588875,237723437,98222239,199224908,446023083,592027951,715014484,722922554,844373999,614840395,724187979,637535504,56279423,433931190,227045118,16341154,353825618,157921761,694228013,611560340,637899838,944211442,605038011,331760910,831045336,938300642,46470173,133128681,963265040,509291125,933604580,222146009,281394777,436004923,513515875,717512410,110396965,808898325,582662765,80639613,40773012,17707869,56389575,137772207,550111583,808275146,846311547,966954926,248179364,737328274,295657928,638615316,84348306,302771922,298933311,886222,448304781,78799169,966180340,469119413,870484732,223782291,865098940,253594390,198852013,621227759,56937446,755905516,138235407,331136551,74861858,363787420,82203509,555369320,921209956,211614200,366939968,734491639,657952295,603902240,570210536,101940569,770676524,79442389,39360645,902375817,700841205,90328640,29997698,98610397,280545473,401159546,130300267,109224685,433741188,328648798,65386480,231920674,207948613,36445022,291623937,558805283,687381628,153979514,215897163,483738758,617196742,879627784,626739740,207521645,302844787,376091719,929148112,838721047,94956599,148188250,311865808,668536376,249408906,720382776,107998093,86224492,209532475,532104823,963854053,25919450,481994387,571345825,209895038,183250223,394948163,21822664,701293858,48595248,135020785,551602263,885308720,616950624,831068430,326441500,474550993,24274393,105313868,69611504,167917269,185006503,640953643,729904549,79163379,999511938,973033710,482570643,312040760,313987346,818003543,142722754,588049935,428492629,955925790,712567901,405391366,594560078,322800033,549440887,66284287,288977394,382535091,494213897,933703930,891921459,881083931,123377183,278595326,630272200,241013327,556828647,32820150,290920927,480734448,870387522,91962537,12090675,137490485,696134379,232577575,304044063,997949206,478000750,815260401,135891747,950453646,84040514,10636228,314919873,104094234,460102180,641704991,472908503,336232374,28034561,670926612,619916065,486132858,52646149,60563679,133987922,810616507,395376581,779793049,36560549,878781157,75360211,711198194,7045934,102390731,539593248,913256433,35244322,438811860,652087222,20889513,843189108,27730181,850179246,753884031,168370295,209079897,722582387,422154524,12598827,733561492,264378617,267750276,100648267,171288211,212875297,880339355,848695302,228535918,95391568,661756223,319032148,854128524,202901251,104777768,649313392,291263868,156597963,67475144,769336748,36663627,670750878,168343443,905261980,609437443,465591958,566607016,21627114,355147233,895468596,368273374,315704742,410485635,314593281,57513431,53572245,386052200,624206391,372176520,343886507,822029072,80311953,976242333,722806229,682278302,636230381,595913632,449661994,474179365,220773538,836594797,866294848,671362254,706321640,5686511,522383418,784957390,786810209,862368084,246232763,26038550,336224440,894687823,337744867,678700648,636141719,105771398,730910117,592854157,568673197,388192829,94535995,521547763,772489334,335085354,77422244,653543404,872620270,756031105,747021014,992781936,885544809,82909731,332919170,970568333,849168697,949456164,351746069,921185139,941998528,712792990,40978542,970061863,133883417,763211110,162280817,942438207,867048424,451812204,105536836,83593877,93942757,81393510,619596587,204611984,585274819,31758251,623453610,812109557,866747814,841910875,19304620,975696221,341257855,739431495,930249854,28346018,463133470,403493562,555917886,758045552,244093391,783856767,615992271,756415088,112677423,274828863,604354322,932923191,654942968,418267232,103391593,181211706,286309874,292177969,487507941,688829660,868733221,57929394,809232867,762859218,897504336,430238624,443114119,93193884,232503234,409099945,293116499,81512475,33084186,433606685,8519102,885100121,258510878,432908665,221336619,562878929,640694668,672279018,81988659,91869017,1826526,633651424,408077695,646534994,839368916,453294069,388921774,461012728,119921120,174602954,882164654,107219468,91797421,738974779,844158630,142617259,376521961,717774465,12766634,406410094,181947329,119528822,462174918,325495627,964154080,773505945,241397255,567055602,118561075,377120265,829030136,428572594,152413898,465371393,361559777,503934676,747574342,702631044,900360233,184659269,247442746,34870008,383145981,24023892,42627208,323430405,406684856,504904969,229924686,814095227,673143730,375796292,51852395,397820661,55256316,772946086,569265277,394841732,173499072,509089056,684914544,846393088,396952288,492896834,65641137,9952157,555156811,851559909,129345533,95395876,295687270,131766310,333710691,241276251,680825021,833256731,805015830,754078710,499878023,286884075,352839588,765584727,253472443,651277500,89772319,62823817,903895151,466483979,880923503,722031081,539267748,92050296,694077610,24199344,636943903,703176004,676589787,518639244,133650735,8383,140893081,463033373,514141861,855545946,403192688,148600931,805344434,981958844,163442491,139340302,928259062,574338157,109895081,756647103,362681165,23749969,526749219,146530799,372374262,726874076,685611196,463099948,840089308,823504178,895593309,523862540,22240727,723701267,692796439,173416239,471419894,86984675,308047696,922037402,233597240,261684542,878566916,124084087,860586128,361669329,990670071,544146684,133443993,820262883,460744488,699557312,134259106,73438701,274129260,938050005,128981408,772503011,564954693,168321864,542583727,782113105,20531026,113065393,914516203,526340820,517998325,892121915,162202051,973123114,44721446,14066472,191993734,318249544,231299909,512169493,918211675,566134383,668018871,141636959,873467615,964972991,504557593,834027195,662280974,341566195,272229512,14218652,40672856,688891046,107469145,993151466,653784578,276559325,977963167,934597278,874035766,923952260,204360941,660962412,655331131,854176901,15973490,823969133,474662475,543447298,470786795,183908017,506052264,978137506,362724135,391441690,218073069,192463832,629252042,629592066,694903071,12820489,164067432,112326876,239679219,756795608,711121053,65042216,888326567,798297625,657840566,873556584,312791327,43865033,652718710,896890094,844091565,369960873,967234446,5609779,380232341,446600293,555778186,557591299,611305363,647468693,706683902,651773004,827773459,989460147,890811908,412729450,371686340,49870904,100134707,484324948,879357484,171753512,236233194,467006833,78596093,848049302,108632153,212474099,579855510,350766484,489685573,988090107,339386098,345582654,411884290,992446327,332910218,820112069,866475815,565390976,703974235,207556322,678639704,404834489,618041505,838152574,485070545,525704381,558786287,368115856,815783363,335379493,371544054,805953749,130792745,357894334,821354869,486400367,608207687,917414267,49000009,56914462,724118497,262730108,271525502,919340817,216271154,326954554,507514983,146757044,672885261,533696525,945785803,941014505,561209027,284917743,516952369,847113668,415817044,725271170,515373818,86210775,186012278,719649961,321973201,537777345,812650839,19634731,81420857,493260460,941673800,904561857,727372064,110855855,286033036,81812644,74047137,117199946,329966701,740545731,329861483,326651874,862823164,304827735,491244050,57104213,972801329,871910470,563840740,773466616,727878399,30893612,685377957,838019369,393777757,471140423,684882872,314081784,257739362,350941135,277561283,430980675,822841972,857820371,122231664,791683825,21369963,535199092,429625608,670551020,749792262,324506838,525446533,520102245,892967003,126189116,294113023,443200745,401633419,504749190,552209258,349655450,143889958,84916162,49771704,580363954,306250204,776360416,971851118,141121144,1120920,304928195,32191623,671707295,62974786,855273978,127193806,68677,947232917]
heaters = [936483963,371295856,574952188,692495863,209581279,559375073,880928992,814284704,562716375,56133237,685993226,795932286,351272217,192584094,295990407,931622575,270326326,92142608,305103169,825495994,12306469,676394371,529249826,17538286,353691741,55334669,942341310,238500545,274174513,344112107,318720978,919261628,32825278,584128645,302386078,49482722,18410774,192233450,52189062,761215636,984087651,435079741,203388952,711633887,887287244,303243718,431452673,165777770,940690231,406103203,673502655,172819248,175210392,353956885,216642583,920089394,705681489,984086889,422272807,853097561,55375286,832012651,370599740,760232458,492200534,307366694,213855023,166725061,829424539,614852874,933922532,478019401,335749180,496927591,91097332,709997191,503646405,197570939,565053511,681672343,41812056,508072623,781594289,97746524,838913,214708909,633085181,274144760,198558505,776184675,520160847,730407170,936779938,257801809,45982795,886206292,315552630,355927967,132363052,418713828,812374555,25601906,232978251,802776076,765238878,883239241,194955423,348727617,582186256,868908860,862410420,164795337,254302907,576500419,943810516,102104248,812619339,490214231,283310525,421726854,60178656,543830811,267017423,313984709,773683484,284833003,447232258,439795706,7717768,863507956,283730066,237522922,668628859,10792109,432823124,931132679,833600264,136324020,980236438,132252260,118159175,626364397,134561363,65526228,433181663,514646711,750625308,86104009,893584832,920106531,993703048,186805017,10828805,611099287,124411586,483937371,807801786,125979546,712332258,94411828,375135219,678616719,225547016,460060957,303375099,492089493,381562832,333326060,219233975,730963220,337872631,678546549,193683473,445900437,678200276,461819034,786604180,547122328,107473889,865862452,994017270,965945455,461869443,633828243,25369559,622889516,68799934,412762161,921460117,475607902,400853358,279165845,481566798,974792090,970892245,205211809,929115359,288241376,542677378,415643237,99064215,110908589,24849727,37534171,269598357,96574576,217218856,868091470,9438572,867773373,898611812,509213511,629146082,996205993,97107270,141798817,91826305,76944520,421392146,84213663,773267824,534264902,761079807,55714717,887357105,684418967,900143615,484422768,582955999,921077579,488742677,966201142,818738627,257872591,442637291,521596629,446296549,893203719,957191281,506838668,162844005,25025757,494081665,858764353,807867962,445221000,789299430,542011069,747384687,662583106,331552847,481614142,623019051,98411032,17763790,641748753,1395015,409654144,17604504,319134020,418807581,240597579,11802952,803718740,428723550,749069165,56317441,279921138,645379436,745258433,433854127,872309502,827920623,315361848,89917118,201493316,63934340,241102389,53693681,72521983,692213941,120790588,548344679,969669254,770733473,96122007,614869105,413738371,148752411,410806569,266080078,946917892,995186574,143601313,883132010,185702584,809590197,326053587,751853212,396133714,413004076,485336806,705785714,233807748,859230273,48650814,630445038,998417946,120684411,556806418,659217347,390794734,875080390,153595005,195905341,488635336,516626024,657200547,61196908,684744421,134619474,249219227,827415117,54752025,94283259,568781105,54318938,50819569,218983255,812079474,6637764,39233551,706769184,730602509,717853795,405603719,868609655,128639279,671813271,489608349,837669986,609643548,634631399,846131991,96640881,538628413,877143764,472983471,596219550,296258526,142931314,798350561,400052271,54703587,866142949,265879408,869224496,517832309,603879719,191700089,470903901,797603490,521910434,70944821,516182462,792188601,708184185,97225621,628935358,602051372,881948187,764025893,971436816,413376949,516783798,161424518,583006443,414384818,276168905,858625168,970574383,950851047,527729602,236937282,563195614,313747100,75156315,224780347,252535534,730012044,531326775,565081777,949717583,450447908,798134081,56640205,409648392,920930640,166622551,899517547,54021196,134615647,977877416,286358799,114460444,384313174,668188889,851645838,426070589,50888803,28094024,877342675,668597001,120849634,747752223,190288295,365202260,239099272,392539545,135347809,398422268,222025508,49113048,809277288,509442965,983590744,28003449,941005806,60499865,61466024,912809739,117592852,136581833,18332235,458185633,997059336,554341189,821281415,44837567,965712119,835158585,557221303,42254954,509408368,402118965,282407646,486446452,235274635,743396318,202058380,823546753,818172756,691718351,381344046,951157052,21283274,18679294,996238952,651049183,754437216,82837424,472160490,442258343,388047112,792954023,42234926,611271281,74652519,554436985,490862562,442391407,476970113,673213518,755744630,227202983,374610915,811079048,372347158,271337148,255663855,620611916,296398733,558928138,604721966,314959889,131148215,328301192,872644801,375345044,57661847,46011241,216814567,870162257,246395907,620516111,626666323,914064351,374515197,202346622,373062753,206419009,98194358,878112588,723622910,523333987,374279975,543937762,124080655,216947348,954328877,643054874,685555614,676416921,553742607,705353398,557807324,94553891,615304413,80487564,425747694,918959832,255507200,489700047,24333203,384723400,120406330,178066345,316340144,352268814,117025766,342985666,506958492,29242326,849501566,894513084,341368719,455239096,512230789,948413547,8351326,774299027,40329616,800980816,657075116,893540316,171926119,989755396,203589488,580053723,180143659,870018190,972545485,73929078,73444558,165546437,140622372,646668013,134557024,199622077,678791525,16027811,736942180,42005589,51771616,187651655,866720,682061158,927153398,525817554,520422673,42970880,657074768,94712902,347340065,676898487,57487781,976977764,198293164,611565782,729363532,576225248,613978813,275964834,369266096,27535642,82550989,953014739,385679047,795074861,972915771,647853517,524948507,739713851,380839852,67103082,958541655,580254369,611938756,555486609,952023954,913424728,361789671,72795840,206982668,981676583,714449158,165928129,113268875,477944392,222556564,384636652,662432694,951062010,778417449,391687819,59795878,759953328,450334987,840733059,551103931,306798806,259295995,743468202,410212768,816463484,674249836,993272080,178955360,225629720,495562016,969219846,14489227,647764656,31461680,495478598,714697167,832226676,465729199,725732856,832479479,419621926,42392112,312634158,697292944,377226707,470517183,740485005,456723248,834053336,101632761,330788271,870792261,97454900,187460217,285356970,663611039,428153602,552866295,9563143,252428032,70709577,295877357,386096294,217810602,430653326,763538270,218407996,733636049,517458116,402763840,383403536,412288552,196943173,751608584,786659634,479137706,596727070,443234000,960550204,125682707,811305057,230418196,518583209,132332715,908839869,967980819,310493839,84689863,748353127,552263588,469801182,798579502,745874942,58102655,219241778,862108241,174018756,653483456,865074234,838360648,687202969,653246417,176127055,727926397,837595998,720632301,6797474,14469383,107225126,979870005,416063770,577027758,69378854,114262504,145481466,709082285,159206792,816907560,902405649,202227629,166125980,350604760,66557599,380543462,380643646,916952487,877798137,88117316,809970738,279355233,724148689,977188474,799233909,7075156,593524885,104180458,554763879,335497657,564547824,565504100,457765656,380956838,885803137,129661133,104717782,995633759,216988667,294272241,971694024,795809580,436436122,170742880,637431768,667293540,835900724,938428172,42383236,163455226,560398869,907999188,516535712,79788988,422199097,614253591,806212808,544335133,153222689,173819848,605403994,40386250,959849876,299709668,371237861,747713870,545689424,646976478,816939563,85775001,658914670,953174758,573129664,126106053,691051760,915367344,6103500,649793091,911114020,180425961,172216963,790024632,845579201,750339008,716710850,316458505,194078494,997072512,775790221,126001988,882493530,192187459,279218325,570619580,888797205,911354481,281391763,385348625,536639601,17940254,312611907,323320387,705095977,526299871,829768482,160073356,703368248,405645979,578873475,818551993,416082247,680549275,286739581,71812577,861150603,465887488,238612432,800154253,442911235,623784721,727619771,333605179,615419714,77889246,59995077,605902205,30905361,882843400,777485255,549667368,932288229,720554869,498376428,819380674,311338285,392391903,801412362,320134150,48123315,198864,194823601,280678910,496351558,147128936,480823164,213953687,31992331,617173945,289457183,649392804,625941352,466894989,198833985,318231163,276875511,642628906,968762379,915775946,224004951,105356844,998930558,791714638,539244054,693825238,284571856,353101923,86703200,19748312,635871655,216278113,89409398,612682933,970946144,111092302,403503980,85518281,77662433,749937702,414411849,523457500,302679319,890038337,296223535,761858999,266692779,300143942,873124969,855594032,418395512,111909906,467093948,395254251,664254964,158677773,870124884,618267896,702643886,116195727,631927144,138369724,2645214,946912267,900647199,358224468,281971135,385435594,205349006,87501691,407601020,77509210,322202388,94755960,278037293,841346157,472528851,190850729,80612263,935606631,658362461,55111261,127985279,417453506,104979171,93831388,209614727,121535609,185010744,712232130,411560532,53034337,142388454,825963620,636267132,420609111,454141231,594787979,65186268,368946306,95276053,74800687,897212914,974760011,431740492,62689478,793543225,207534705,315322785,433385277,789303562,611457593,851493234,8738808,637236638,328205855,63294420,784911675,18478204,325529460,178280242,616339729,508195822,497694813,100895604,33313876,560565712,210140773,18351074,336339197,468903653,391690059,97443558,144318870,496684136,501337863,407116260,313061056,75211620,6807835,602649554,198174826,770142663,903796572,957150373,26319334,114898903,104021224,818980266,24131970,859094154,55866075,76725942,481192503,126466966,107444188,573699167,107808386,45302590,984397670,350601780,661967670,725338230,287946169,230605692,374861187,722433258,856205646,107857422,869450642,23700837,55492764,451960328,240551835,35962122,972479647,114873459,676383916,146511219,836271780,86820492,489086240,652518611,474288426,53761765,69326124,21007972,332140805,980511082,807731743,96250492,65306362,239882517,878657800,504087828,174116359,146413430,901742195,581953064,37596788,114980854,333888034,74396405,337874859,508971123,643276838,914115846,239991662,358552746,149867118,611312873,773689263,381960656,784124509,820964771,165452800,566865313,67857499,960147714,10505640,267611004,700365988,486269687,204847505,455730394,534046756,35162210,413260545,707865417,34659139,548080836,37248669,913617184,448914016,580793579,877485216,916799941,254419740,185607581,5853354,740556563,511914907,934352067,254763205,515772895,351046973,701875480,86497967,717880928,861628050,900404629,930822841,714098870,721088654,879766335,600861328,1210080,448935246,144627611,597748251,426353891,724399645,693017250,382598000,758546882,434517182,131373005,372905919,72498687,655183138,159837128,28051546,601888438,291000096,811327831,258675745,56344687,737844660,384622842,223306602,105623436,391596430,316799533,837790218,837404194,437444698,296515605,21207126,93364927,959739288,588540799,295530711,2467913,114498007,222655937,261820085,9154470,33333284,886755968,964022574,710768250,223428067,354107113,594040932,187447799,869626222,34211672,617437555,424983159,954321969,881457187,101723481,855519311,103021890,55559257,776529601,667859766,615042871,186739886,856634313,515507681,981541147,585659953,269275870,764481439,37863850,515546016,478353845,661782194,548505323,374645668,247689072,86925218,456237544,113277149,178532001,345664526,433401925,714601429,577663179,804459944,1237296,467881049,384653807,950756779,90850973,657387350,698806213,247956448,285746356,558549178,677992187,259434505,716900703,212350582,5894007,862285043,998046323,962762522,7910756,398047134,359599311,559615897,278985597,954127378,758449897,951973934,865717166,699679115,679413411,730647578,682349900,692094320,257804088,84285948,402204663,368228863,922113434,363983417,435862863,273397102,163067312,483179212,157346777,767890160,346179228,701085273,44895869,236583695,269931268,42337390,185900082,981455436,292598823,763845109,287505197,261640229,488303394,25622702,144023114,175385407,466696,401308731,342685268,107641669,390773618,727205200,808361323,147204739,961865607,965845880,935796065,901717474,166467217,436302656,429568534,711308302,64652512,574000958,530537360,182285754,10481787,73735055,167005066,93017633,126746462,509966166,187095363,388685311,781746381,506473121,816051586,193931091,667153938,637093557,70927135,11912438,289344873,909282281,606643293,394448073,206744622,128321108,619280568,542753014,332352420,242157093,452750986,851260381,597167153,397258040,982198335,100621856,81903603,809816472,981573865,135551379,524855964,538848719,284859412,684066899,277904033,103634053,754248210,846675807,853643227,990954229,25022896,238975416,458375400,684484589,855568922,143855389,296893557,78479096,29164370,125252230,18729059,246682151,136451725,417564235,818517827,48875707,115254395,843345749,719933243,995147903,848162885,77159409,885547922,135229922,210074037,251224191,372128135,885184881,683072198,739833502,451351984,960553884,394553889,630689065,11833863,323239917,352636687,857416336,774066360,70357572,29201685,166448279,118011690,295067649,455214398,97131503,401599201,136668686,330586959,427803702,114547936,854791218,603381074,607929584,892809509,774154752,408478269,936531271,18917765,123296599,71703685,971464984,886796525,852685495,926738034,134729394,387634529,655627552,186652285,384324306,855284413,302574851,134244661,392188077,670676074,704091193,25785781,382903151,592252445,193117848,676859297,546305098,50169739,827687258,688163587,411462545,553650475,156890874,902484449,172114160,855193189,123878152,108446721,243402122,50600566,626145706,753989020,785436771,253832088,253380074,891810295,367255652,390720264,623463100,971607987,349785721,185871008,138303649,892122689,175210669,565633846,845428100,3763079,969042990,189554082,117207673,459834390,435925755,537444368,304252272,202350575,84995755,447029030,319110004,808149247,523305632,252222559,764808513,447050696,328745397,895947295,823832879,332125144,510275233,86617138,366282856,73323421,838607016,325921229,320290884,534868006,953009078,290534620,430523640,938410737,749353191,534975129,605941692,694563370,952938145,891342267,91043644,600641553,809440371,748390230,382875131,121320305,861363710,545588121,737355535,753833555,320020163,279827453,863794219,799985013,100483271,338662664,71729298,608964097,745495255,119154187,962640483,749779861,116083231,95711941,958319362,346164634,455803915,622230556,731077449,110235787,601968395,280332326,759260142,537376120,511713205,484808778,628175128,709767644,940617270,120309901,704867789,193132871,929350858,744284353,887855674,473933562,177508389,321686818,19505558,412398962,52604043,938845293,610484942,536533406,233120889,52609295,234137079,951845449,60774840,33498486,368338688,620458562,659440280,49683793,811853915,510634945,896867203,459362528,302297131,909055562,91144354,145790876,28411705,774156301,789017381,96580820,529183186,252024875,737300819,627200321,151550502,193681772,771816799,916691491,579184237,599077986,300373566,437448243,356096420,668585329,279183399,776596876,5572113,747179879,515342344,350205835,449770996,158692332,114817997,744234082,397456046,15117883,683189235,913895783,836360115,69478121,635159326,774561423,7968247,778341215,257906628,807675728,154806387,21228370,888886344,262030007,596851299,176645734,855429762,597971847,36848216,271149485,249095461,101785024,96893934,142217821,105618436,307561430,984794259,780643584,299116765,789230306,734749070,689627818,398472845,72073147,738561877,346965657,826674172,486591292,522116868,600018834,80820373,576817616,832489554,795973873,257246348,447768003,647105911,844836347,795588643,225136679,798956517,994420175,147635202,961227729,982448569,804315978,876568028,534006754,510332243,897300561,300359493,200923332,74147840,455210198,26542103,564010192,119457664,620727481,91216041,912160776,593384877,105571071,511497875,367746184,252178422,377503023,819592901,730753827,113571774,480822013,194608830,173011429,110229165,490672441,187489985,578646324,148308783,544685361,597053744,638676624,907730440,294655370,968492186,669609489,105349921,528070628,880615392,838576798,25068725,423266263,370243377,65806811,60994272,781029885,349226731,173839244,931392566,699532357,360335352,252376524,412036043,602496773,570846784,57942470,29001199,737342302,531426524,94079573,440397797,182621548,566225673,54846254,323484993,176661725,331211921,194121801,370428192,24508869,396679637,205418771,112558399,983402633,806884097,734766052,182065714,607236801,986623863,466026954,435133847,905727072,983787746,837027347,546228110,110737492,882663251,104226081,528571062,346969973,106234606,719090963,516828403,911100753,104931139,79536142,467583669,36060510,271581694,863759761,13827985,271688597,512994835,550327718,145888797,674169952,443640270,991774084,126445421,745337373,613115060,998275114,867590634,974801086,329109439,571950248,423992742,488252626,319848573,336376548,96661910,537557747,269350900,85048424,332236913,241293169,758144425,905851902,934321909,540876277,2288366,598840294,600451416,554270037,625429751,812856639,183548037,105340767,728724419,365049870,825364189,299048550,790224448,56403066,364515444,787706064,532112471,92393989,28074920,201756678,47808533,359130153,471433401,106975402,77726031,109819150,42001277,186321254,470158652,364126851,344569385,561741383,642290447,368227838,904886259,737145537,371880816,23461742,124968971,700445987,683329233,119358522,894910112,571767374,852418140,521248421,829394212,105146985,619313992,104510182,446962784,998692060,285267468,306834572,653393735,150111965,785994177,825198720,458473292,182271786,923205258,534400209,680679487,327729018,639029549,603911396,931116850,567562261,44044300,956649041,190366998,894985003,830460411,844884402,603249028,329094687,116991962,774841838,425935858,140969955,400549622,469242187,993485125,819140450,923365880,86490516,385630549,979968975,286473982,902857478,206183044,427297897,203417889,843472977,710770592,617295130,178729831,375626042,692449361,575505812,52814774,540138985,495523604,116607940,117540094,397361774,578172026,121221954,1357031,125762125,146083383,88083069,795907900,148438137,571254392,466159185,717078039,252374509,378169938,498036493,401060423,818845075,46944127,301917549,971871829,282189499,907995695,457828861,88738204,862322188,474858691,900787385,921351992,451329605,584430031,72813286,293176168,877347936,757018628,164450899,114805804,100832822,125620449,119439920,322504073,77229883,922520793,122520258,347115889,56656102,883850693,734210952,442434602,409969900,29548302,135546413,234370980,381030840,982071104,109734086,759814276,53750248,875759905,43806797,821429905,393025350,64842925,479304955,467218788,345956484,45372737,808853230,617729678,39727126,412349621,223329856,496453414,918560503,133919285,804518095,771559731,891116909,243913963,708672596,716014710,708356829,496864613,387131155,430850253,132828134,645412414,506541101,811107799,62586637,774104676,714334584,33261489,680097403,489082887,241659671,682514020,302975513,218698532,114685885,671311345,998177724,23735482,283266210,31429718,544250420,876934945,258329832,330530768,837906634,292019190,966392935,747236284,315857532,37964940,274103421,503773932,547938650,587990792,434476228,797564196,68517598,524034794,622346411,530768787,776912049,860233783,89279277,218717864,646620231,124463528,209442918,381425393,377893856,152893613,85490457,757508112,948757546,494975225,489936675,913394127,201983733,361933202,337637710,818175174,525336255,814143546,337757516,891292391,252777712,505330396,583120265,534412594,888834182,532826920,8215028,424000766,623111994,158515317,287210539,397269095,375021142,115829649,128726561,784256776,541987524,706168941,232252996,498317173,823481889,875487155,547643419,128032091,56739143,132037133,797486980,918231933,906610589,7693858,254631164,444043455,532674860,954531324,898097956,462770307,742263962,290882489,982190629,764085692,36016384,884461081,48562411,937634395,586275079,870280317,290168102,67411624,701756108,434717832,563235330,188275334,100126507,139486126,877134314,668662390,219842557,14961237,783880716,663998045,490112503,366546607,565724253,10393480,175516462,410129503,417028629,761027442,968594740,245750920,517637837,275851040,604213985,721762879,326564028,740900511,997681649,276137545,124536226,76773135,835891745,787518119,875309572,64994654,88952033,368200319,442374426,191570446,439477647,897529674,649072968,545424994,497668762,663056447,697060446,971621537,577520571,909636004,109214813,267822484,166764476,344388797,674082514,328574873,970412652,380121777,90339861,657062554,682410782,360833025,26832047,142131706,244240787,113657692,924845839,190357665,383620203,758843527,125262403,189706670,534270542,648849865,90700167,477295977,62063894,223792594,38261461,755743152,202362237,635504058,126021206,619533300,495452444,68105467,625757174,666382637,558739532,582304571,709945418,633497594,117624179,663094722,340348371,131614367,134509759,552722869,391980939,691296424,525446476,519144246,824263339,124415423,986899339,800984792,369394679,41146476,59087798,951176072,547973836,386383316,746822062,943962966,369364104,674756098,557577857,739890738,58812367,616974549,440197327,108289552,896830033,627624916,52289148,502898813,872199146,120650978,349403056,989849872,643963973,932396978,400815665,645659594,365928067,907340708,186880587,73912373,438178554,745531515,728576007,18173033,284466335,520072701,396420995,946368549,145291939,818669290,240009279,654641665,796718652,682823697,858244489,14953371,651676854,359264056,219952406,920731155,108845450,295368062,61804748,517798135,822495879,128981192,768872699,827326672,715740557,395634652,615203630,386627683,913436006,551339017,110405561,746349875,243345576,893210522,71529302,188093550,985345044,447752491,386395727,955413739,903482754,125262188,186093165,931634123,671434984,928694750,454495432,898371823,125190751,132935153,651102169,290467849,662808512,824984195,354940333,565583943,6708379,871554787,28327500,151901444,796996672,60538543,150000679,708588953,457710456,246189016,290782721,659894922,41379524,266915396,746700567,49480148,122633203,97898857,206594575,546943404,247781868,292042521,4011983,857405224,794328398,519035434,142943702,213577099,145128756,430557678,510487403,357591034,18759063,750959379,405868012,808593390,545566092,367114132,366698693,974350008,130754659,156256441,976987253,357774787,959612087,598157239,857764266,386296351,639706376,241924550,632346657,746673774,599170197,495658774,240926483,37703764,765442839,16244474,290451349,385493012,22889685,307362982,151467439,738104156,96499751,521161572,724228138,957982748,131144077,613258895,61204890,611876473,301674806,39573875,545670202,116890902,223810065,124875136,123361142,8994239,635298161,960477621,112801648,776721282,594475039,248054629,581369354,817117406,134320077,512221142,786276418,126372266,77347779,756515218,648078686,14396596,90915439,154910256,619471006,241455764,195911296,588721021,177038218,9457409,622840341,35294287,71552193,572822587,53008786,505931375,300861152,42371557,321671342,906884073,102150730,446358666,789720491,383353777,368967617,98944961,815616749,682581642,292014820,892946345,133495179,326040916,538891715,7493184,822365471,291719005,216150934,453900661,639473861,274507170,847132434,85722275,358705944,577182257,311538478,255046938,989506132,516198156,55957659,468494583,106385157,747412904,136826225,476356216,299886296,44857363,150939844,667771001,477674585,982877609,779761739,510333379,916393313,69695307,990437134,131163241,935348243,610602639,367183238,528163235,82556172,833103998,178494524,715788587,55391215,99731354,940600596,840069983,144203834,272284222,786245975,969221834,47901543,567844154,339369010,58384638,18067834,309365320,445023853,977838517,632583306,783571292,905959818,600582474,609478196,796022560,75528757,834940678,982804226,339392236,448744020,78175876,789439615,750616717,89198719,805241783,49682065,428306350,179639706,990014707,266862171,999631639,837364770,922329177,842492371,55089657,326413342,355804556,58194375,967801240,794298302,13211962,655608271,862596518,145060776,80996396,949279021,669470962,924610279,526268039,294768058,69460824,782922156,940370723,478583188,14361279,290321198,345528802,506793726,762008880,638259099,332838706,618209885,727653009,892236245,729241292,669221215,229101166,858096469,674664878,171926964,3957311,524490076,477314975,381363280,126939243,16595630,542857878,301823090,177277994,744405347,773918185,81969063,555497623,137136252,392012711,870783359,154860408,136180739,158069827,35289628,200269802,620665943,997409100,990373796,66641475,204290238,472657091,405718184,644939263,144226832,304306539,321437466,123613788,960248267,553016264,235124832,373140944,727596568,943632358,462307811,411544631,933269877,39243629,83171552,645398845,278486918,162764013,473578791,864344555,459547577,57910605,79403300,382391822,588280530,9135500,861988141,302981703,322733862,437304890,94246196,93346911,656944376,50698205,326702154,914900546,543542680,719367000,68236390,92739232,742628149,969322457,591588657,128756236,928499432,673774522,240099201,18477072,99482514,698808941,293805944,931596355,36668208,102248814,94856454,258029813,937583798,883374947,121261096,659216625,378660080,938897077,126313561,31155069,223191971,326503866,729757777,759850022,861554692,460455301,488663766,787427612,147137001,177898110,429276724,101824926,974548270,167976799,38043566,595570603,126824532,29110078,212766586,200717225,550569716,65665536,420026150,393733939,882174944,280163498,69251593,122870524,791585610,518154105,569854150,909117077,977543312,320545234,160256093,479661713,20799553,685736457,420877928,31686325,562076975,840134250,431360725,122396450,413758480,279702952,918789559,688696183,772868929,626992647,956140878,239606045,526960190,397353102,786926791,319773042,421432100,401215472,922764902,930292927,397768860,184636909,78659648,330261031,244899100,440506048,1996105,774755539,122992212,43817248,435553371,366732352,392573174,907571834,130953044,343029489,96008006,846337945,617647534,659132918,326301600,270735340,878495034,708941891,740067059,874755767,347128607,624912597,356478880,8644677,848155499,100506554,729980045,200541004,90812085,210818156,20213989,20054053,479493348,131551223,220732198,934771995,515537091,682856439,408539283,607488500,714940240,622587293,77283845,267933636,680391071,129793669,184766687,905333425,17234980,550995093,625042187,741519432,662468661,201054310,128011439,502619557,473710848,729321485,662519897,269199184,830124906,501019161,345659040,548220145,231131385,620248850,636799412,776704483,312134246,885206548,692724398,110106799,227045657,25400127,136645892,740466779,150398866,958466921,678705100,710966483,407646451,634046605,400412399,310418873,972219948,45079660,178075385,113770355,877910655,831723695,602062120,708084754,573572451,771071152,476525666,793327377,520239594,260929421,72150151,92305880,901732026,618064103,424978582,84417752,469950844,811960020,500963102,196454005,120096596,621839370,598865288,666020505,121859371,184027737,577724079,35027666,92441762,830995731,104589407,192540203,558314370,233562847,683641391,923347087,977657987,100404312,366103820,566254085,532366738,863870742,731602005,691018960,157076322,517320269,233452958,191242037,569379947,174616775,114454201,72365651,566730733,746433664,504103652,647091749,813837035,835699502,58478734,97550590,2743469,805305474,120136702,88879490,734927274,744240221,146129150,418815529,374179615,4670889,987198709,183024019,681083407,673961517,87956872,822398568,847980284,303151696,32322566,517961227,268615829,615612009,14824017,39150667,875264287,303889659,757386247,255077560,504170086,409142918,222385132,5367744,814338812,679130953,278343266,895888496,190103155,401037927,440754803,887854096,92907047,268127560,999209514,392182258,779897563,645643700,891776187,794002496,336567814,223323700,747494591,155234565,627681428,2086332,498222150,373913975,628005281,795611340,606605158,900996775,938581006,109075558,429352415,373963563,313947150,142429371,513655639,919042311,641731753,715676015,103855836,393809219,206943679,326388460,730591360,530472552,447562767,345188106,223166995,54215881,111719148,763012958,333928869,760710250,79999737,816773893,596326605,948048264,665995955,502226099,96291761,758914445,169697582,41956036,573439414,682601940,633163306,794213057,727982894,787141077,773794197,791081325,632570698,571668636,985907152,157683412,190285086,518290019,706677101,537468597,711469075,264775607,290488843,808633248,67975851,8827553,188311628,710119765,61758907,747348448,53514233,765549585,810324496,575493576,54185744,166733080,964199872,188627020,361440746,296359237,895118866,139833627,629637749,315213605,100385733,846825145,216083346,110927723,139413443,10056202,156357479,527649272,34314619,638657646,795788616,291115596,812074106,270922857,528104537,96018886,822176683,59221314,47695837,405510706,98318742,28172251,837598795,560620058,123533995,205124472,608726047,39556199,41568248,143832370,471539715,746311153,592544922,20832915,891946522,509339194,386995194,293237373,113041793,956344512,514599036,742330161,256005435,273601104,444245279,422742112,150772108,789094274,595942893,941451621,317883051,868608068,894945148,367638848,595665917,935788352,417580014,290736902,889814989,44402415,94563396,982076370,198239748,68308139,91603253,416055428,229802342,905343266,975611245,853528448,854842154,666483848,319330584,427491435,515748830,739565096,28198214,126475289,808855340,653192448,62048650,115070333,690277940,794676486,926899509,553672425,525804524,301427463,177447368,650611940,641123634,439459639,594869218,76065072,672895139,699716071,507554325,660494391,586258194,586494122,256768724,217297445,41453146,918323194,292950569,587694259,893097038,164203714,255334803,739707315,478010722,189881227,173082747,308870791,516388116,746626663,600354198,67810758,967550305,871801051,79340676,38880392,66193165,111995009,104441491,646978216,846150129,401486247,178713033,93302056,464592882,162027282,183264178,629489848,331430214,568004958,894518191,781707137,639877791,975412808,665881436,932010335,551979127,131316096,2393512,218545469,896661113,290575192,112417244,403989126,649432515,145880482,534419747,9054653,296171190,675075162,832140633,374109567,620352731,235243732,224009597,390463588,958981931,537522160,464218769,316761032,190703911,115030853,381242649,246977673,15344107,776325865,391152461,651968560,174020926,689954646,803525169,115837978,268712064,878528585,479854970,914364883,130589227,877829533,468306241,295426232,246489360,250718457,462191385,602256496,34499961,813238415,512111397,734770781,261546017,697860888,539748349,372555293,267473377,741774068,854190041,443838892,389551813,312659966,131048000,791471334,745001020,402481130,719842438,616471915,227857208,632752255,328129841,140232191,92873378,495231255,852570660,937168414,137445578,941382430,302473561,372325856,706293012,524535715,244369648,924919450,280054095,732504088,465437343,469981427,325968501,114791388,651521688,898872741,954184989,372212905,162430624,519782231,16480421,108528931,270600523,760109362,570809709,789328014,229443779,173942219,721631166,614852353,925166085,484786315,43618065,589873406,10798668,543060237,407903509,866474539,750966666,735362043,461468216,332856995,925593108,71827288,315419802,270971418,196785617,251048539,714912265,152411468,424530383,141471747,244233178,778751807,361770362,748269477,500863107,17826756,552534668,730875448,217193696,799732419,795598138,384719144,694370669,861696085,43868874,155747906,19974096,135656049,491066076,360862489,315012073,653699634,996389164,235200042,637195414,635354087,107447325,626422726,321918288,762338201,523684783,975141053,393462445,821164002,573465992,129298386,657501316,821254197,734868288,545841097,694155873,546587007,345763361,154059545,560978180,700039508,294087621,370774400,400775784,329884696,362287696,853167427,436634570,565596191,212560515,32249222,285268619,326179429,364890990,657056745,584778919,139617892,505768320,500857992,577353882,255577628,318878374,62627484,313136558,551195156,485512312,715052831,367420583,15231934,38517901,416257869,691766004,827742948,476661770,140365080,971833732,641893220,488989659,822260322,671963409,72515490,144612581,345139041,398531540,118097787,594616281,474425276,851810999,261469291,555810653,748759099,140005473,577391246,529049307,149404169,420463618,156324027,965421508,600331871,692560869,302137121,12746070,622317437,836781347,706673404,475333118,77525964,249281797,86050529,433219981,158657337,172151963,697569632,939576051,7432766,161425214,594704115,596146245,64221391,332127743,553956626,800382015,975939875,141383339,112864991,486822014,897872806,180662973,8194000,863561748,980790788,859278122,59870379,219113057,491672972,30566748,486742003,907632998,11452745,5735563,908326873,581486566,994120912,560372902,117066750,445846598,773328203,756076177,711567540,126698284,700238520,698420080,200670058,112339016,236694777,782381373,234344008,927712436,331634632,856174637,232184090,340214031,375750703,285638072,93125059,430266528,912096647,870073843,114926878,781218471,16802917,879246840,459643451,521781276,47669962,177651003,778138091,138968854,773278398,66487189,197162592,144416423,550300251,831734575,784922280,989695017,543304704,14671662,418982407,238435936,188291050,364265319,524317414,77373457,981063942,155210106,216599015,394863440,745366850,108534999,727090468,820522824,180100512,144846561,130157254,853088841,263323315,504137316,212882597,3030455,186228235,54271966,261361165,93042040,182449842,620825156,732839766,812210195,56181964,504947915,597213039,20980395,430180657,616346397,265759829,6943890,180315801,468241490,354639822,957346507,968238403,344740833,148300625,407573855,413925633,148581198,473691903,617934292,390728752,120625985,722324283,172146468,398193745,676206741,316214641,390423540,285895195,912602604,576737132,272773544,774851310,378110340,289351485,20410165,22216791,528430337,483793614,539161534,99890176,669459725,735750020,332725292,859544434,240808869,415470335,133562526,103436876,149304509,892961645,36137210,767700016,445396314,440834534,287430788,158531813,209953742,376909773,793279808,868231058,989019,235551735,105648724,462106777,327733487,714140032,265414741,502017168,86777160,908288963,91816843,710895264,565173787,348646006,3528757,325760430,912709385,223921752,854514898,254238128,635243413,40327985,335095090,34033774,213463025,375370685,341126487,679013166,239159382,255324668,569368370,187063558,61160098,420583820,29075394,191359089,34684195,969197028,630987101,725957621,315137540,614939856,248345359,379722592,469183438,6090682,434360965,800801180,578395089,220769432,767585255,664091834,711919157,239369193,841155920,422699239,430205597,35512977,452107729,570436795,757191935,929738001,15567235,438492289,723508366,745676626,665467868,423623900,938597495,740711250,964255669,333428621,942976702,973094232,706785319,1783454,495697476,891390997,555543685,556795217,470962140,628942716,725717278,570660033,214185707,429563755,630987649,735167857,492751408,768950002,979074546,286191308,446922854,682093619,472725425,199702653,33032357,562516682,994860280,309050418,594916880,877120306,433229934,118915986,899658501,128067780,656564166,102959676,364433628,412624552,756149301,940562608,201605667,450228881,411914586,354147552,480720627,431076553,286779871,955988029,965640196,773832371,432671743,327334437,449757623,81415968,997048193,367060788,263124663,667381868,379967195,639763834,853116087,721246837,243380722,690930766,822283411,852998810,543150876,931273182,840529116,418401224,890068,512944503,851881441,90882916,401274773,919436809,475103629,722493057,68268861,431457907,253745608,947394361,58761400,907855827,254551032,244748578,851145019,598740244,711889644,97849271,373202673,765075871,291064239,96400654,441595449,191227311,321880065,119924240,20019372,896609781,427838268,902520120,978658079,729081380,129063878,218114076,88689903,257548703,441502616,571445305,527350329,304946912,139746820,963651078,909485919,734219865,592235393,113546306,407286406,25221231,277424467,486019232,644922683,658545350,833959390,877187408,206508179,242369479,520333772,696295420,998731437,947076707,369422985,516885418,721868211,303900374,730451830,332875489,443443188,181405626,250556020,27080020,453320132,472457546,346932663,272144014,577253766,720411663,238996833,818330919,995458823,424322962,950314294,889435097,894987090,72558042,505278976,73409394,929050158,985386747,1171165,356417332,974207441,89136159,108300932,733588624,720386141,17070001,280181756,376113799,300246672,452224432,591401891,137263721,386900547,849988891,702071193,435384133,817316580,127332426,620844879,64324227,351482257,782264149,411643887,99476753,163510305,131606553,3179861,904316299,895246052,922943660,432689917,632784855,669016619,730918419,939407293,318600707,45350578,643448339,856070928,636630574,86527864,220359807,118447399,614051380,348114756,19249664,52050729,790757974,640461382,839387088,551689451,203193789,579012993,222968794,870535321,281053036,341836299,516900146,762380285,83506924,194050177,166643624,460712880,522826725,438662129,283041952,409809159,682479384,720848261,341469900,801283094,87989099,9532688,302097338,491596836,691411221,307356008,827233999,305669093,392541005,159886029,495425584,616669447,400293885,466037722,823133045,307433341,186507505,452995562,459860497,874706104,659926213,419803714,157240803,134268789,236180882,735282696,68345412,363545495,311137328,955369829,165487384,355140023,981311548,228778276,80756602,859523488,36253094,6352266,181330890,348973137,413673602,207663475,332076528,693186121,280350672,274622786,642806899,812807083,498143992,60312469,59385099,652946685,226477203,854306915,53635141,295661625,55255864,410844253,899435066,667763029,343689181,800538284,454869311,739705235,443052162,51882585,905223991,325461389,181694592,812240288,916460084,984894082,103863676,525576099,757255782,209835952,337675468,305290233,674513348,127150970,866081181,375228279,95192492,24896029,815731885,263167325,29897033,115743880,273164134,542541430,278248848,456488817,41455166,952273334,809787094,133312750,761945429,571838142,894332269,804399730,136704245,573722003,344129391,609213166,991135713,780257190,247443748,51710622,955504075,274276259,261178551,964310767,111977060,802772648,707624482,73210466,733150909,953644724,29397285,744887341,284856755,846432122,52996726,303238955,558422354,900966288,633207419,535620248,711038490,824889522,556749800,707638621,517866061,23665936,468911657,880718356,421609099,435575440,737646035,193816114,882219146,23066512,570284233,547587470,335180895,328674762,501763428,762631205,360257139,878312858,794593506,679738296,541517410,247413884,756807796,122986191,149643723,151680402,22406003,561032774,470117219,667762420,333453718,571803403,103452474,56955026,612899067,308542988,656475458,405022898,844169343,322670650,729405875,287884049,979533430,408720108,706152050,95849606,917549948,974885507,747973186,609046142,331446992,849992804,767836984,806955265,137908050,478719815,15683974,607546084,535270881,488699684,598122860,72934991,398209878,154375494,221660660,359563653,167333313,314897668,878378446,896931022,177463392,919927308,128985734,52231515,327239560,209664953,965683991,362411289,782911331,758434948,700726091,96069867,531530703,52037448,6017716,208021403,112342905,509078622,509550306,994692353,427163554,300020157,147175543,825673504,848233392,262170558,457103240,985149361,306391957,11319440,705740653,830972590,70163689,65577398,293195853,60710084,299649463,359372426,248348418,76630136,579991199,276786438,293062642,116800101,845201305,486986808,727103339,243867143,69252503,576638403,760918888,498632731,39119323,141444257,782208748,835024349,241579076,120932433,991871369,614030769,1705679,750059542,521714504,279938027,929232859,908558807,184634010,29936155,625783687,319008050,94608369,944959003,284393856,301918148,981939222,833655537,65297331,881077078,362703881,51032712,860815431,127618978,703483540,195874976,125774428,205376257,752530670,251773507,807526137,788114097,154493583,265920258,408306799,202118628,481629820,886519197,486601093,686842275,33513300,410296164,70616409,84507850,836744283,438243825,488036143,183407508,683932089,159636010,795344967,424641441,653518484,99284761,84184408,843105530,770518382,569033442,793358181,37962422,24761973,355631271,647782096,679080829,228887776,773639455,692321247,569777461,413183632,208167204,415336665,241475905,534421083,238530227,418534818,305742201,473783514,10156722,52818541,603450954,427897675,900973569,548557764,256021555,190024875,439891036,609929078,931545393,120612099,488942281,25978276,677704391,71919496,303633167,534471075,724240702,376167318,52256858,107684430,109457745,55813314,751498306,873679513,231375383,780661011,237507285,760322869,11738211,301573909,284260221,203398350,869586073,152406007,687252425,129948340,50881381,464878961,675189741,610386239,232137154,698844326,681500217,89352599,658062140,509604930,765274274,685161235,697561431,801741844,562770830,764337000,757761224,114865058,742209731,733927141,760368997,994032929,81642621,72964361,684810046,30557427,916041112,385682619,855109465,657191109,695551020,17997450,835431570,643291482,12753907,754033896,539667703,17137971,275069899,714984149,213082209,417447114,997548827,398303260,576363121,783726677,222548219,598887306,36077031,549250141,7899912,777318517,42269096,185566471,462401231,627149502,651940638,704735872,123487499,778171269,342086431,425901376,354409559,234799913,354678252,455755870,962221888,156904637,133799190,933565077,705702735,986663342,129550507,392910247,923285382,88065699,89927466,168390730,552530942,668252566,128886599,972026726,945081153,189885259,33827149,242705366,77640709,30317365,590329216,288684172,749320231,981016409,710828044,228385825,720262164,873850787,169515276,479927810,991103116,586904480,504183267,630675985,939481950,218855837,818048795,548768049,495314256,100084820,438852717,131749399,842466092,760902151,10312550,169831021,344203084,847771417,733186252,400170878,900647789,368140598,438643579,118755749,354038889,801905233,806861037,701701701,313277961,780271730,137312459,413061535,303566572,769713979,934334103,952842257,634257720,8159979,291770801,879664884,43258018,626509349,630307402,39674763,93811171,224332677,170996785,609845809,886548379,770041545,144768571,612357902,950601068,266794774,73911682,988091408,361252005,626177966,503204262,356408126,612460777,532137546,159324445,1322953,198508110,283700979,541636291,890941782,802543190,791586101,526406342,826248001,913869883,401058815,437314350,253240416,692061936,713526200,686158552,279599074,527417082,633886005,848691846,377472348,511059598,591559233,279721999,445933910,93297340,385331070,596097785,397237818,642327181,192637598,402253557,189990321,652120536,580797911,950293140,533899819,860559345,911527448,40964485,733805864,76571527,594949736,636352520,708241580,61863386,941800510,532188111,216191822,141105277,172917760,683417929,462588547,627885867,936103889,632864501,67164716,408467137,394930678,875435916,833953193,418529360,214009595,617133018,956102163,381901618,939356490,257733264,248452049,25377775,115480897,148176147,108450687,664563753,53527202,629014499,932174159,950864026,391362586,36055788,985197618,910425934,500666441,652923519,837126241,415360990,295801111,104629772,870954758,681058332,252525992,569639650,244477802,595180081,5772219,169899196,135515240,271972860,995635782,250989228,511050866,90295440,472005298,981430046,72890515,5206815,257088756,153624328,688737002,665935284,837033671,652515578,777817864,844859537,185342973,1037639,845686653,54296056,20746864,238665943,906535052,531122077,626711207,520946092,250139425,467818796,485851283,762666065,591644090,912935020,75706972,535232889,997651787,774246911,164416004,321304117,384405861,871474229,821872841,394999761,682008828,47643088,873463332,892988610,843843034,280846228,806476468,680701459,697012422,957460747,947807858,920459607,485400439,982286967,235754811,223779762,822594037,985744120,358066813,779747197,265925985,297539066,42646977,655687988,54916490,710962867,346872339,258278546,823072035,429521918,75316837,420684885,934696271,597348892,156778119,7411164,5381822,257969180,66008614,743687155,795188545,943140534,786156431,611739473,146599453,733263462,697839348,970704147,984310948,247570195,29421704,7813827,330487922,117793912,575335028,684436802,52412813,433852821,57380982,974985549,281895433,260595727,906206034,443767492,982510591,53741154,77422116,444370686,382973914,634082539,211376559,460853553,385129120,349407782,276301176,727198796,493707873,664388081,602996614,381739883,14054923,145373338,39258636,335394201,618741410,71059096,82297318,984533536,693639417,456445603,462641115,363912596,245574316,51443125,754649290,352197848,924300204,964309877,889997408,962834901,76900962,482291418,268578548,782008820,622318100,54945810,849239038,984193704,424533934,994131982,746426392,381883148,628931200,325146444,183381271,449988252,662630277,769850775,293002250,308813179,902608301,106211077,323639060,618582147,541809502,861636834,48037317,702314125,223374963,254566763,509139495,178137748,368926718,766060537,14981594,333042237,891471755,765359744,121655525,845933887,62074247,190774043,939234308,706209106,907306151,960586157,582461131,193765691,827738363,192580253,231434720,423432901,668939527,789738244,681728448,777747369,660050072,708523349,148082606,683790747,286089732,887218669,505208762,686301274,530844081,249399729,566144937,845399949,678112869,140253232,92004396,129657732,609083666,607607791,779401852,904163511,474821783,73453207,517931602,125213523,722685579,9018821,255469257,644970624,316806090,947993717,749224526,519986121,88754582,783082165,482158339,972382020,267035048,610208084,532853363,452642529,968885807,488241626,341992995,210027593,263618461,376710266,587649306,344593389,965176611,424810217,549674491,697499421,907023421,149205272,579590455,983932971,337361697,474191977,225722000,46511976,628690280,570971298,3165621,664984619,684571123,162462213,50698554,332567797,714514685,912735349,867320122,77778265,987715988,494019006,805654540,751459445,427564108,589680294,119670353,254929279,159494966,365280684,409687793,790164669,258718835,780558317,659012874,456205739,726214161,124816604,287097465,644318024,440481194,584274927,258958936,520968530,420233469,583177078,341785038,9861588,973425853,630867103,649613460,39539450,760067805,19844857,111019823,894359565,56142180,274771736,998725902,854049962,237014786,72826764,519700914,590247827,861241474,638651316,482378884,384114541,270226283,558203554,518561982,775570526,581071770,465095481,812252665,124480323,77673639,376750453,56050793,886314074,334066126,920105002,968005145,73845990,469963120,18282752,981029921,937924228,955509594,160012670,476397224,782086330,570523601,275678152,200474085,759083030,855622030,681936476,979106671,826116183,845888404,297641466,763683777,516460498,22688712,224577065,130942254,161681959,614850036,886224266,972146717,607264821,103050934,105228256,985235689,402801584,17766944,901779453,415169692,375622919,285456031,181045619,996874381,593286151,593766836,82705043,601738092,911618521,424144749,895550628,599501551,976779580,14898323,288011609,975950703,323369535,738147835,830612704,464010628,906481117,772120179,573148210,437808675,764404681,895275791,275283386,8092864,518274065,231516801,655484621,138916037,447109570,525262137,922947389,495363220,568517699,922221590,388782731,271600674,389778043,967423929,688261844,62867944,645537640,256709414,13452853,409296014,440964535,117852526,560460526,589763318,160549652,118540532,238875486,133356959,150461023,210161042,359012157,635758276,103695838,206711549,365441775,176682005,672057881,305801325,674502004,936492362,512457849,115138604,251751481,644356577,88441465,962975687,88586195,100485503,937702379,728882167,868836859,445268191,789459989,93042535,983747885,167083520,57088942,716141632,339546167,888378690,674328886,967360361,619874468,787012079,960229880,243985955,125663562,844040111,298152073,962542460,456812369,391447758,320057945,560324458,657373511,820719209,333259560,249052122,166365029,866312587,176523049,147968036,905696404,675372092,527675849,333510611,380520407,200179683,460540979,574148843,868556908,35099028,498844318,93273316,774538280,766487493,393875076,313802278,648027892,515206907,221399823,270643488,334738470,689793797,40598251,20961967,913439839,970265317,51346079,832607306,420526668,216005377,947986387,419007794,458093823,246987244,821698835,972469635,592096706,77601191,159116917,660883504,683629444,722553858,90151268,634863650,454607254,630280530,735520706,773612188,27023356,500968284,638052948,15542496,377208985,172663529,498503384,805646519,409629076,596286628,630659894,314535444,439952041,280735044,85290627,900954018,219964107,910368440,534364783,292296127,325905800,60975681,468570948,449389487,189121510,289421010,248454615,68504537,97497145,897471932,33108243,837932684,729841540,20171116,861014033,111017723,297538374,31016533,603827557,315013355,882267630,44958522,289592666,778971938,914028432,918308211,834109866,111270246,808251632,96606680,170833628,15149757,218895553,131050538,41148922,100197720,395900792,272738,81918850,66072801,29499486,522117323,607666019,758039848,148226263,157771721,674494449,455010408,170660289,396808478,16344389,408196263,137318654,517180900,38561822,715964607,659254286,11628507,605262428,808570135,361740729,250227646,803065496,187069877,167363531,822771594,467955903,642724985,229057063,116857348,221394478,180810073,185536406,164120198,999165038,792157773,190057989,996438034,56558132,30247481,563272475,605549927,345598534,324274381,913509028,778619771,290124957,342273609,276834728,311694094,723001403,815084073,112809276,550420009,697023634,145900831,521920321,591620699,312781061,664302949,172183090,220721121,748600856,420877597,26123208,404566377,613871837,832524271,379462492,392650032,51840593,553969516,17024245,97117820,757586176,113295547,133242118,722317052,50615051,76616523,144176086,244397095,593242601,654800564,526871920,854261437,289286395,133463957,155797831,504558502,494799689,41691839,428047729,920942431,364793888,818042009,641737169,13724149,674000592,744690397,476807663,444905084,774666512,774199070,153330895,844954443,987449537,103722921,307390461,613306992,722087522,694893057,51536613,532923528,484422037,570670082,590100672,742512458,379408889,846249480,130816279,753430272,131977370,379007395,333769341,227006801,17842266,374737729,440453230,321305401,405986049,644957602,97945336,194788550,839060400,356011529,596327361,167775778,161472335,593688184,701263104,531712770,610048801,796246207,184891523,62989852,108488240,734190533,892231047,996383575,934244297,590956462,886368037,93538620,145556736,388188019,220715747,865301460,362380736,269407060,28929544,680520364,800832404,310198279,205158815,392950270,595951943,93554971,213346571,211106885,430431351,534793161,842572810,407027930,975982393,648961943,826911466,534329325,489332099,489703530,82871984,698505341,633651685,205442900,518094502,715590176,808643410,238768585,484155499,178911788,286293694,20240709,883179937,198233095,956491168,831962781,325413228,372252665,830676944,396208661,879659727,956584319,43046569,367653300,631539259,61637470,853840436,10478598,813116110,604014909,316354772,598121610,258947663,331503219,794999993,714609295,709867041,109193933,271397393,913696501,989016257,665782197,57079040,549718718,440822610,880002698,485468397,976973426,332405820,139650893,705911058,547485778,419022029,904362890,885322411,492550192,889101406,729093394,123961754,159040466,168950125,571369541,608489850,364760514,257125191,765987373,932797893,696543129,659987884,456308211,300977418,996454219,121558005,206915247,848531836,983151572,882269164,716235391,122375102,261984066,824720912,224910246,288264380,929305606,190755411,980591353,802341371,694581462,902505320,729914479,246056889,217607879,170971512,185082498,125223030,882469728,146652314,267193220,328142663,355731545,185603567,292895125,448825529,93592570,52294386,383912457,21284142,240289192,64172162,90693096,151432258,146817089,889082998,626731560,70040385,347712139,694916686,448669216,761407273,909963416,524082425,68375559,284268968,704914248,619464215,334340849,449428591,639321016,608549,76421964,21706620,543920928,988635264,704883787,107506188,822754589,389174290,764586915,663115335,686791062,965754987,762662483,885946485,243943675,415063602,947073358,313136342,547564844,747884291,262471524,220471508,848322459,404614558,69144835,328588818,411807689,705013320,491588741,555358556,740299408,484878116,793538894,927722166,140661673,868726411,736452302,605582053,885540216,5715180,4223301,907038134,750991732,949624883,39922655,758143299,886927220,694771291,945477676,57291310,822373314,423536306,613888784,910331078,53905296,334167994,484716831,23284124,80205470,979561130,874274008,840139682,522656349,77141413,228584081,111888531,900822901,370785757,946157952,753271807,823161184,780365514,920561569,406097195,365504777,28535197,140676207,112999349,242988204,536331681,930674686,371541432,761885795,362548082,934507635,721910934,667440766,369865881,163682480,84889553,809575663,81780649,97833663,465384086,367869606,972026907,948123220,778297800,528230723,276364763,2926927,386695364,696445504,19204509,647635713,366305395,452136394,259230872,441924519,426939507,622408100,213070741,17683016,284180135,211898017,842084993,5243621,875687198,969303895,279617123,830766625,903477228,677881637,755925724,330387616,579434617,512247352,79304241,426517347,969615921,228870811,281487278,843185583,175506928,249891565,242498001,887424448,461747699,380655413,321741878,151920400,115590164,837142969,696508486,77742983,749236483,366442351,960977308,714085047,488765493,349669654,28111517,23863879,648256011,847214224,105861736,540210745,908615346,134884983,62156627,989377547,502553708,366986705,372516751,974203052,15370236,422497390,125675326,687252590,487226564,254693715,495338112,146527543,672155739,950500731,727914462,991509522,620414112,266874199,54302588,130530188,678539638,77530296,322089721,703150407,39359586,884577204,59779447,838302580,504232671,668030435,543014529,787172800,159479011,304146421,777817887,52267520,932375595,248453006,41462074,861354668,393619227,101694007,360149793,74148636,675609992,231093855,136965787,467469681,60726419,12665317,265101766,684297284,2501081,671952583,38046555,84280235,99164850,802281034,680497503,771112646,819410255,15527574,126414931,587397012,192234003,854461911,511169266,80244240,631168520,273078038,450031027,234066055,905628728,330920138,939597283,9773921,61533075,39735896,559747011,335134948,910948602,695212929,778152954,241287648,872374400,125682731,18729847,259926067,388648649,165568147,712523764,811064454,127065800,996155482,602673962,608400082,3513385,505876735,382526672,707220833,731532664,525604773,239179700,596809294,825172768,22298028,893780596,915344785,774438034,874631549,406880328,849740648,824818386,715672117,245363572,656952364,184952521,881161816,432390378,893400176,171098208,166978523,794393079,251623932,441102759,293499647,871608548,138910049,139447832,588032125,129159959,478442374,2205450,352754729,339359514,46269013,840178433,966922984,858813817,639209410,124846507,203720030,833610892,314948816,945044304,363542694,264060921,16179476,345513610,44440360,377799942,721964662,570447262,933110804,513187365,845717203,922254975,595379357,414541726,558816592,877451991,358387366,517809105,213890091,756112937,329392860,685934632,811142928,652999740,325194010,982823033,9986554,926245768,96644251,595268003,335993626,310364219,846628748,62722614,911986468,958757615,62410442,398752467,683734229,129170284,651974649,276358749,547344560,547559819,663429116,311035966,399262342,308763697,70964327,636998382,618804557,777865656,855121103,852790975,345035325,595838953,342015688,236923775,543204887,691552412,739890920,416376310,180415175,138420308,143800364,933614873,749645529,798827532,974052927,432681586,492765738,9794312,842718121,908807682,427013910,725415674,796568899,520430095,167712434,244333374,315262332,564835353,103036709,304622190,184132882,197412447,48762114,353580491,333039566,846580258,40729762,645310188,728890944,16351898,534400026,677603806,174365979,46809476,747848330,12580066,418245365,735872924,457910595,669462964,790187893,442023181,730646672,460101336,627519883,434483164,914137548,811758598,263147195,46077192,118231602,134634848,507610045,242475362,506930775,710886354,60918348,652458864,617604244,79041535,744658408,86652187,955351399,648712952,144108445,816564946,232038023,32749609,666864831,280060924,847279091,48597758,531711424,587426579,689166572,88762264,473720030,883643359,190010639,200626584,381671498,219213297,383428074,470193649,952321430,263631497,388784896,307987829,915852733,721585482,640019943,862572756,745692842,938010180,459642633,715054572,603702992,723438116,564984876,675607545,982945704,569729335,958835019,215855823,581915956,413922632,891121969,328957383,956807281,495401609,213721622,72138101,244286599,529114907,104459722,160408055,679181978,928899019,592677221,96898561,574488879,141091019,287788623,523192295,140346178,861169240,779119547,99925601,117364053,147650825,16782068,174332628,840784288,619131156,179069177,784046970,310745376,810283506,241079715,318106694,332408675,980613456,26342845,362564633,212680292,897857614,718309607,623985062,947267311,70915697,26695394,992888382,172594015,684686655,104208537,672182563,608353121,214239858,192195965,422178667,270886581,125435227,508402482,676062139,240393896,883470065,779447097,517112579,244795844,852566103,860578915,240440438,311196390,155046285,758226762,142206214,703518165,132322420,735811804,578150402,403282317,507511887,94722572,155358686,920804497,986999375,127784775,781023581,36253981,21260075,628773701,825544398,32853919,272519354,797647274,110304475,608923964,425484993,798711419,22541736,901835080,202609034,488453943,408416098,891623274,371477352,684893235,488252725,528533888,76691624,258914946,574607178,981858665,834239107,135940086,969908641,499143488,33477634,810857702,154173652,331290882,373735681,133406739,780092061,412582870,848578505,620033808,317555812,456648067,570486269,795722875,126668834,205272370,153985508,109616899,583230945,247127707,34976829,238024303,859909807,732160517,340511909,87218955,743602940,527270687,113887465,137168287,137446378,161849452,489442662,993430802,699112367,98519432,899180365,681970616,759919073,874611202,64908299,139572264,177372033,384456595,931181989,307848365,719364932,33479514,49476284,471733799,67818716,101300411,394454184,309452199,905199206,701878472,136784511,922752665,370120599,504265681,15808083,984435909,200306075,82822607,430152593,144674749,389996617,346029853,131001873,370719914,632513229,398765731,552157208,829356169,820263353,114138709,626385392,694445750,123582452,19541271,451100862,827892302,632349379,792422428,697652349,975295601,50488456,303439427,780271611,135312426,10761609,481736115,525535615,76841194,832275711,496881866,322597257,643373371,389062330,675853773,33353828,877533907,942171000,316562600,150624581,457091632,790053705,541230534,868339893,682695217,53386198,761148987,863917908,731342389,622620142,481893341,20549350,421036861,407905962,907702110,25534482,808793221,609158415,70935656,155124885,931773315,863351281,945460635,918366870,819991679,990564732,921197758,6602414,445106101,5675584,338733329,111912306,861935817,423572235,70263840,955836677,214845710,991837363,42491927,990224863,503986769,830122815,820380793,87952789,192249096,315151384,847615964,267971328,520901937,655509987,358220977,16276476,266782472,14635615,606119056,528036471,99517271,282969840,138285000,17162455,686572487,794153678,730000041,536613776,583899479,391255341,233589073,331443195,140681694,643692867,316380661,240259455,771403825,625309836,944928881,571111980,220124348,663076702,830464809,918801588,536362517,655956760,277200200,11731057,388358053,930993538,642541124,640893952,519656490,50635081,620282155,196556547,489014921,246838756,473544666,290805680,45766835,990007375,143633247,65341679,626433914,155449935,306942793,324780435,474318949,419278179,914508646,606351743,143839586,238313958,285690451,973458912,39006069,592489348,86800697,717918166,487487116,338823885,279381929,172828361,121351161,25455433,273195256,65608884,822381055,346617871,276402164,484041887,623939973,396477910,109960376,706576521,994504184,559574465,730121620,225486960,243678343,250595972,551069637,877903195,351838406,325609451,522688979,271048754,703593191,245800755,207731035,674578870,873874155,355239830,304262728,378084567,856184674,755381018,558427040,979723890,462297681,34268299,214662475,852668943,648548570,676307465,861599262,416564713,406442171,75570537,389653491,228583534,748190033,313131446,110772703,35981019,728555035,20201698,813479216,57265088,967617316,643549859,414833921,27287016,198861101,566948353,109005710,48395657,282483564,762400278,419529275,839711824,921581531,14224284,696856371,836700306,492100964,574355929,54084016,397452809,108197271,138841844,140610044,439471317,998162786,127177585,165915839,113732267,30744217,114958417,956789375,401476889,228454549,82327854,143247019,223480046,80234519,29314164,347872694,245880924,555131418,70274689,138175820,329657842,51541234,817610097,972526773,552415072,661287701,827496060,415161026,229973457,486305777,18433557,575147331,677296970,666845690,751336715,512324645,378367692,319699255,974272569,36258808,663913955,869790451,646924828,155879435,83098352,208105023,517744245,916766649,49386165,543060922,419416304,88491874,17221172,111902615,344554111,305031265,409984044,119782863,998401202,839268003,697711503,969496879,21110495,469287710,758590186,807822441,680149553,218084290,735560248,290710935,453387620,813749784,516755592,480344854,557910683,684224957,786901192,244035718,607525234,539350000,119954591,382644982,548173356,237727240,955117838,18220519,82563537,956887553,697049466,787080677,113156466,736169976,155496265,731106034,945168951,311001176,814546812,27503306,125036993,696208094,678527002,658135622,390111835,342036554,942123706,669175989,261966362,320148362,79962977,198948573,889606610,837143856,711416295,377702147,78324097,133106315,25833187,179655793,905883847,678242946,178973724,179768399,5474311,250905312,100674654,969279589,664084759,800031054,726810711,620635641,695144808,987748376,38364122,333682932,922214385,60666874,159376149,515807012,569946323,310785041,476933161,52161254,500868002,100097021,289409855,60972530,415612091,575593393,377304994,993308214,786259498,196502895,587285757,676876287,38877450,371252040,986020323,705243340,62567587,99426257,314824033,995300070,51128585,910626451,575788366,713753980,219489718,734268527,55592558,188735861,250269208,501598030,130270666,173247169,570322629,192909042,314940502,805310906,63948679,43624453,697236522,428942153,128162492,100905103,547468638,130950049,854219015,723783488,74684786,535221963,814018505,383677076,714708038,14935573,352545868,123999981,801521655,802516532,698050164,218921365,564872822,585294545,570314555,850187902,544860354,597698870,743891071,720416041,519599301,236943205,662743475,524885914,42218369,332997782,351337992,505085941,769532374,384087584,817159984,849928523,834949864,137193328,996783974,428320771,422013453,789102177,374263545,267798752,915384399,85725463,619308082,5180812,613034913,798728132,96415705,49062675,548615433,77780791,591696961,447032848,383279130,114375488,310962751,523242906,990965255,417358300,652335576,692986475,12846222,596561963,963247945,221975460,562461381,65416373,88837394,27419802,283111756,228499918,697360990,727897251,347739176,149327545,132644050,260522764,34421962,295287800,67346383,166777112,556762049,913507564,961035745,903257128,480649653,592721604,488338573,971381224,626525852,700651901,996642184,985718466,281405104,609570812,205136025,9918740,141000939,566792641,993942842,715034059,258941001,219534985,140565927,52501967,577759030,622449123,902544302,30579884,707518755,650761846,220131551,784137523,685186000,113786786,947045050,630342364,627281097,716174156,93198457,870888136,915847447,278238611,284435558,2803662,669485578,377282813,266007078,867490539,439988068,886240833,896083217,167811708,765347845,921669032,484853591,26842150,164449180,85914571,857184013,371402415,218405654,694274055,385388234,202348064,42793378,968765948,621255060,368301706,998902088,667724417,487715875,95630526,944482526,866179505,880276100,785568517,320603463,345932318,846236197,55052545,288629114,616939003,842775705,876621970,293126301,246254689,601570254,238248902,339777906,281227347,769492560,714933686,719455637,557958449,339544472,859890825,767635112,354554786,882651524,700108970,668556877,800990635,822103049,969138323,791815813,885187210,722215701,494692441,32153281,381798370,997045932,536081583,229266316,486288872,527289800,642141078,5266702,470630987,712726608,132317690,217841185,590156738,684813720,92306345,348020790,587446749,28163762,340419103,527428513,826006822,7858077,74197672,145252975,725327833,113203790,93070935,313583038,465249928,467581169,994043010,605579057,835186444,818426094,447581401,658369744,384538064,945926403,156595058,18650809,517491557,964806727,5125839,836587349,741116312,329681762,246543252,949459879,414184074,197231791,100422594,466347972,388032432,900732332,789054799,725465146,273539734,767304758,244746049,808640116,183406327,871104444,256368709,729674859,159225774,342959456,273468444,569133728,538402758,586548895,970317113,921881451,114517499,136215137,736197013,255402055,870011679,863115108,123584671,470878848,583559141,320666938,412756643,621697669,10275159,895905553,476780154,775539899,66323781,159774474,975025768,957856166,944142628,241459691,261912385,767461992,739894240,117670481,2818927,719023011,522242786,361817591,187542211,663430128,328044650,648889279,753131265,401534015,981549809,731242187,86008775,878944150,667299915,150066771,819397197,589040346,101482552,515235746,913118318,861429164,852694921,878139394,26667705,527519359,998350475,779677892,894095428,118780337,121794474,33766083,9347682,340185143,890230087,578503560,250862951,536196974,814137784,240915582,61512079,686856124,59252021,2261895,153942197,736193991,204611301,780817060,67244250,36184937,422364058,239269471,105590491,276363324,978741654,779221336,17714746,24487667,394842692,189633792,102388574,503340549,499500088,377381471,924152084,267835615,387457193,822625047,359445543,329742190,469178070,708849284,538126279,27712214,341186455,332390273,671331042,974720134,116032822,41466456,935002942,102096026,88475029,941128679,332647798,704586423,552160381,675663358,773511148,683349145,99514437,442360224,159898854,917996781,249378219,204626367,34031322,526757330,75830954,471514716,533174382,760062990,938919152,497328086,379765856,196321486,833311988,379215160,885213471,809079259,328653209,346543579,382281589,883078146,427893983,484417056,486954415,182674188,450946153,375181786,461268288,913129324,46407006,218964559,143350733,966601244,746296931,708020837,292298010,3048312,840855903,468259392,655518736,505265420,638552280,965364479,434824046,993868959,827787547,226237163,114921929,343535559,366096977,244222362,596967295,978706859,548926840,16630946,136413890,136176459,86135867,74517169,220071760,572208764,473903860,678306875,460449849,42526933,785592127,510395311,957284437,925027913,310013158,388797462,519184591,709363176,585174535,346285063,332370471,545540250,287292707,778266671,798024198,357320271,910496263,535202297,483492043,765625031,137883193,267969638,492498107,13708811,416214826,761320881,605456719,926535325,668261456,923795760,76054157,75403890,883784656,417305671,122305042,24947871,125513888,121447771,63222547,369920742,292752729,410081026,956780759,256667777,668164863,447840856,724062635,678362543,41556856,306872095,136559149,637082247,880839965,672512984,512266505,194187290,323618168,621955372,46522186,214332594,957831339,733896661,602596706,102937068,131944619,828561338,346440618,592278287,627444342,105327802,156316595,840511884,335804422,277896238,972623488,30420430,968037602,471867142,13947223,335259438,855768385,994241314,436485669,3479309,287666472,617684085,273445575,977753023,550190717,138280284,85384290,120642990,8127318,742837374,545304807,270664431,686727471,251486119,272363315,115562026,364227603,244929671,599807776,681052214,356722188,802954939,269400603,713385323,258901038,340855422,63685936,922670146,337728835,409250824,35961274,396700820,561441452,896317424,956645110,917277259,41273847,638285704,779988941,826928677,469089533,575312994,314111364,547869000,417383242,278557192,989354062,107841313,12749523,680352008,118756759,932540450,871687344,315750774,391166881,894325500,690633147,322189594,234232271,197232324,109380725,701800399,972095247,742208531,713758741,92486423,434129511,412742518,384298794,71999160,56588859,546676170,51347324,499026952,222340729,52065101,825286756,790610697,312660490,785349799,939577331,28945726,952491238,970110906,751127696,87288184,907134743,20194126,686216612,48392072,15209047,860877514,171047959,115422158,722476265,786045717,898452922,133716575,545054772,717798549,270062775,312113314,178897355,250739685,818970381,212499844,12551725,296423247,616429867,875661541,538086696,569462155,763308053,644118171,229035470,108448866,279453137,222137570,139560504,334226782,325283100,687180085,61613607,245753573,562226808,210893834,937629066,289689154,253162107,523406220,588300006,336468632,496834051,666454199,613998419,812504298,58708860,463289556,879347317,876743,496012650,100574543,872671168,463990144,769227951,562617517,542110478,625173172,440995611,847168280,540702350,581085993,349636373,823262819,341061312,583616941,292111538,163980702,595117991,109709236,780633835,135265322,12063259,883731195,873291713,510576793,712485117,368545747,805531881,837413279,944641362,33747441,50536657,906532212,483390197,408404378,694645234,181342746,341215507,820667237,459766156,643621986,479588763,942212550,221914872,691642512,899696551,767574130,684135381,635902429,733496731,116402715,608785744,42883678,777427910,940375022,550836481,899712528,36099569,928046307,293532166,418155381,16490414,128997635,252251622,253270354,195229902,666928876,356465239,424875321,496393772,63641056,754329142,59416284,29589333,239197274,892175512,63006830,39332417,427947821,596293744,750258506,363713736,198301590,753181564,453930730,144843544,724945466,483717631,262115253,882097174,327588177,419398509,789411309,481899197,118971142,33686815,31595475,596687516,925933569,144482952,668453154,998180399,68694207,137797188,408440759,306100701,56642073,648065290,143755093,758702332,545176616,618147010,463891462,258163224,825317406,305745247,524977636,436306376,137585505,707178363,17739374,792915532,40811620,873613947,483912690,600009641,926313622,89582782,231780527,147465278,838755864,680125918,613829423,119672173,285518019,15856513,798398919,5783755,9279679,344742369,967094755,805306789,142237907,29160994,68511798,12511350,410819200,271347873,81413861,375678688,429787036,443209191,189080272,743817591,632921328,815234683,496627899,349141182,90522270,782348392,680032341,395585853,2060259,267034661,958208844,429150833,133458536,64687084,362073984,201772068,306468263,146310735,968725908,302807849,548253331,788888487,77743009,749673465,268347884,200206266,552816391,170826615,690260844,507344014,420764708,921776363,348303483,43700706,624315624,60571904,917720428,899680642,500191567,468672211,796811659,305530121,411343670,703201997,113454138,651197408,98171144,487954890,610766915,187707745,150592772,276982838,298990148,15683456,598840058,241979895,769551494,350932355,129995823,641906740,361715230,969149600,626843283,947768846,57763501,754510019,951932376,374273282,431448511,450332105,792295285,353738526,48671586,625054973,956413734,323508121,565374021,773516619,420795173,640823040,682343575,585790045,308248467,794406883,483627760,899137003,100669129,314894423,823839731,92781639,307878951,233423834,494733547,77526892,57857271,390040184,285281844,193946935,933444046,819018365,664461863,695567041,641767466,168420759,264249767,249651973,865147620,717254081,63628756,754624464,82430913,875359632,551848005,75032289,80737590,332967382,633383770,204584211,325515430,296983101,435961457,782982813,959832922,807742368,481846289,22724964,479359360,381603623,18900397,417349779,509123129,50558033,911293575,257744621,439329148,756212050,847701404,910982830,477504347,62149768,667076912,342517575,436709065,463128587,321424981,61262040,424912876,127580657,852401071,234369738,360156546,187646307,265487953,377986183,557149855,988912065,269132322,499353850,67043052,156638867,961970094,219970173,219341124,29827747,951254078,859020678,820954943,207295026,789026548,457672011,954548970,47190631,711469474,478503022,21516386,287120315,235379396,356630798,266963209,757315080,58973791,182544070,57031505,750797973,47622439,526415589,627157261,782346151,996872923,568781545,61714018,785877603,220444571,395592300,903393566,626279472,61731957,87378376,482529462,974416762,312226912,295160363,865974949,944292124,813576738,755855117,291179414,530158163,458594138,272868283,219646036,859516437,917746937,138195983,668537383,473354977,397669951,462735571,951434588,390863532,883884729,306254004,485721947,943420982,204678673,558633195,149603681,833199577,637407130,253202674,57732142,788985797,565748532,625472055,169354898,724916989,798083270,995638306,500431518,206561374,136417844,848126268,609221137,770599241,135052077,516000416,673003704,169862957,673930014,705969598,176862489,203463753,614309225,386748377,794456417,168662051,24677117,283961548,833073602,22134021,77777172,969345937,986217017,70617173,97348398,899469819,44835278,365714405,256785699,148091201,35268334,49402966,386961820,879804202,89808350,875418256,537141573,510144001,235505983,129673438,518549339,770101047,204356460,792671667,591644928,719997864,726727981,377676178,434841692,497466703,769039550,691129204,862463583,58305878,132822023,104231328,262252322,38332210,797337948,560934756,177233762,208019545,81115499,803559495,692755060,625443033,681582144,673321110,416559727,115621047,563214972,993602075,430214031,822758146,448956789,506700812,140865507,438070664,79707932,414395974,463667797,793992863,967644561,308477996,564154914,611338093,197561803,204483337,570588337,9191035,2386308,890446419,66911837,891770587,699883296,170621253,533709004,801015287,88945566,259509450,36039093,118647597,245338363,26243279,629621096,35326634,29251066,641889677,429442458,739832617,436477789,78061571,15799127,833912417,87712197,798091715,137573421,149577506,393276352,633961176,319112265,846149874,397200462,14484889,781877312,559546791,472026124,538474050,637269892,94127255,94305524,150010382,78688696,818470767,50916865,61258549,720744708,394033207,824026348,81769911,710338675,800517052,305044509,839597374,145504028,88281819,634310434,746640530,40438289,834469349,503628664,253903021,91045936,993668266,395202521,1850276,32817674,456328217,844239682,711879645,929796078,991667374,125949029,199433039,796597153,788273651,481612592,389946779,508402587,32331943,675560466,191688951,283707535,651822983,667770512,262434540,598881420,144172451,744830141,678001424,621702186,440697447,923871804,206642018,344317905,275579248,685678204,589303404,20709642,967580858,385305322,956329727,59086119,361430628,480811080,803836477,260045662,458219589,420274181,474445084,391745477,28853884,201881322,788195172,517121108,181121325,914760054,329777283,704481052,135695053,792101235,594328892,939245647,896783679,996036885,549876408,943634793,296211434,351456070,135117818,473425756,439768957,705630972,928026248,956400553,308996476,688313686,141197860,728960241,33542930,908287574,68471920,342281804,414568093,208988183,121607414,37332310,171887824,346131331,689058972,782317780,165536457,179909934,882264340,989663492,806442607,904578210,2216935,191278055,27250826,590615771,809846763,343191055,18469190,612504671,476885426,397362756,594676500,339042362,10862643,825309484,379621615,126568068,220708346,533891431,719582229,183601477,3506847,395992569,395285130,390259739,473354013,26962934,46982221,503689898,928557790,507113781,846205971,192539094,894180476,193677004,337175954,854398092,438563333,770061227,682585367,147599473,153709004,757381465,174706486,474743331,902394090,800934094,664797040,679414517,749236120,714846479,46746166,831280807,600894445,764828921,435542883,544965605,12147358,942678019,602601414,182064424,585555771,665772643,43988609,20650404,326472861,1635320,360514407,114270262,482891594,411296923,710503746,427381702,464444877,969474541,793159376,991614081,230253578,106353552,777754160,128691478,987595373,407304926,189003224,448871855,79215074,75371225,334784001,100528245,301562104,292875008,317740532,620774882,680863226,120863097,974024864,961026745,751994128,824046701,630864204,807911389,27614942,267862442,838338582,316339707,699429224,774462668,495676609,747700750,679686653,821037156,234543848,345961091,122802586,797235291,776040782,42213421,249836746,675660137,73880870,56191280,99995436,84059476,329330562,786375793,796567891,296467217,355433657,266945823,465108578,239395366,281045531,8678342,413963154,424691576,703158851,181277894,251247943,771327999,498385901,978593385,434747900,68588206,356238381,114061631,478419093,403900261,948857038,226675044,91474730,964979505,407016969,791760866,109176628,419025767,967187456,215848849,464703938,674040405,620848910,132073244,842878066,449519650,22265982,355183474,357087436,499227134,84810887,280414779,352069135,701483038,933176214,819554657,295008341,812929911,415030541,184395709,112757120,821317764,655755210,391738066,904297207,574366808,236927369,396587823,455279451,397498696,86441502,561852251,565186698,772662605,306788826,91562135,286511693,536666255,111408963,637679535,536546215,241380330,75575705,831017136,464343242,261295096,130104004,105599738,431777653,539770758,956204778,313573345,95318255,784089701,235946715,94605221,330524076,725434190,900745889,16907298,131589591,865583174,595159218,655127778,583906677,866737196,663454149,731765597,938520988,454858101,905803834,126443033,59707326,64638442,899052959,481120199,704232216,41454273,375738192,429870764,495920618,346771297,707549299,164114854,702327008,85394475,705865129,775557075,709505882,481645561,151078184,638346312,651143950,199702538,31099552,290117752,221179174,857163039,18892397,489915201,552480609,969789482,643921822,223965121,435934034,676589521,307147160,464609310,438132678,121977230,810378881,696563693,212628454,26616348,457340838,476470231,861631332,955565203,301654555,492193896,195801828,896375992,793513839,713644203,521951326,112721734,19563840,830418045,132839040,35730978,382609733,748721991,309309895,660979525,942949322,867423641,315633382,565643184,2371866,647719725,630811432,68456032,75252188,688634211,85810594,50104799,883724325,550806201,390796568,112925850,362195580,452457462,5948385,983237511,179162290,201513514,48897057,119578776,863278287,511629055,217983375,832460421,306335542,63152535,340712705,960008611,613063744,928785680,42293717,13414462,118563546,418650362,893185140,644934028,849220765,470057971,464959862,34892848,767017861,717835464,97514602,397893153,126145713,564638802,154109121,246718365,952121845,56690049,454397922,407004900,588917183,971944236,706155370,4165199,285022889,136657544,143323365,152122199,212258663,253989952,404611606,374035640,525345289,965977984,8584346,188677451,61550916,546611005,749097747,536695115,596458983,25441663,41762866,474314871,350739233,31678016,983954103,338022152,44062349,467020006,152511057,305344128,225821544,779085759,886555754,101014592,33145192,311450880,137292421,869261447,138867766,428797451,991123272,571161303,256117431,8434229,813144679,84174092,108198027,358569358,636086424,530933402,603134129,752492263,606267058,868022438,789679973,495346329,284630662,341454365,540186349,144086705,451180766,23355183,334031858,551184148,655005925,476385531,585562079,417286130,793879455,209079952,516485350,233354854,482870334,53980103,798470665,64135130,675317694,613408663,637893441,629675641,952064449,446540546,699094004,582871069,286637647,713112908,182410849,319974874,311633808,709774601,57543569,205596542,159893371,825844000,773297439,239025629,509326713,177227027,887802978,588271890,70944442,509812609,108251580,51613207,465733817,803347582,633121985,99731010,141840410,997901278,26979923,918473500,464638442,720732780,193559311,861098419,381809578,185418788,127776697,852278057,521378509,75321003,845207916,598097885,7685235,902682981,213874190,843369899,918800871,524311898,984666045,773234533,329248134,401008397,944444093,220236074,38866868,400421788,822724865,682581600,291308926,913887769,701668817,908080220,730956889,585972583,874175917,339007892,224503931,901779116,409505733,670744474,60711415,114998158,831737784,45877365,907222860,560714320,767333204,929859393,908318932,802527248,523648907,579194543,126795997,195017264,595110726,194627803,284869218,848876341,123774744,956425621,730314352,524271459,97986350,529605779,912094485,626715687,596241452,871386862,708000741,954544538,327207076,456684943,397282623,602386238,67590108,761074471,966032565,132948635,877694143,133268736,815180709,943991950,856498192,582227103,555424389,699270992,617046160,289258335,454838115,569899132,310624482,925901695,963281703,143851235,227077279,202366012,344445414,625644433,919028297,51693386,227345114,408901563,253877519,662433822,970020306,582918565,84902919,827196603,677154521,420188994,983169400,34420713,835822348,975667809,11221018,199045746,375309574,668538979,500178949,256601485,346973797,963483152,27615862,869282038,484940703,490933534,280712742,710460913,707487471,124971658,159649240,17701577,950639931,919965215,120593752,180584252,478108731,482613421,238032028,989743882,10073690,450278295,94932037,89879785,367016163,867617357,630955969,202722097,241220137,530695601,901380016,144282974,247885133,880133729,540222767,110669100,880682554,967368532,757204465,347351133,69939785,597390164,643415201,92099140,160493649,970276689,596980352,198155858,451347487,884972805,266194513,722743290,978967598,636199919,83938798,655600485,86242285,508579426,502476300,6452674,514383077,614695964,444219809,349172891,268950364,943174460,1845644,954967650,995999519,921866046,855605664,406873114,521473528,317800267,270235958,720811279,719913426,662083584,526021181,440792946,735944919,313425491,112324793,790627394,238781900,707940704,92986326,39043222,9898397,444591069,146488770,813476506,11718118,963870858,308361085,539693962,458472984,384116652,512727282,703036810,277618454,244370025,138277111,239077101,19911548,438916882,269708329,797390333,86864382,788271961,453208762,748145603,566396436,777376348,866751066,103588661,198366288,47582272,644307398,54868590,344381076,544315667,33079049,908795617,17216033,25531442,403194872,185307419,403481561,354217079,501777269,202278314,225010197,27678612,337964132,861898787,155714094,97190743,397245881,777842022,457904465,211930985,396178169,12675614,438163445,491594552,860045455,71534228,832411323,274124034,850216623,234595623,68659869,767699844,649526932,939768423,93145323,563822154,106586645,400380917,135805968,508765993,697645644,862604666,134520565,734339311,245259246,844007507,897660292,696886047,980959769,758879564,583452615,677768103,995243433,306251948,805671824,834930211,806885357,755942872,618594052,741896837,770084977,81751617,195849995,351413692,629892194,651208495,77488931,419846744,880446013,139307592,585523514,123629244,12995837,963657621,19454120,133837652,432512264,1475953,184021954,273507776,23165230,81954012,864061957,4890285,379619987,892184850,219950596,683289063,89716263,327712047,708303021,739997204,848186429,265841995,33402783,345815523,30746279,2130804,452684476,526405389,810230930,150413461,203765086,236362015,839122802,404801943,71040883,776191427,633641711,37809882,608505840,840525866,570799896,624400923,701213619,700018375,293410359,518428779,684311352,91458310,689008565,728105909,707170535,33657825,337339123,301812181,200951853,553500287,573143383,356681286,908493603,236234029,481040678,722227838,698679000,50349782,913207734,216760229,956903491,171940854,444427963,345628453,827123014,794849267,683346129,48824525,48017099,362510199,297808054,623066068,534120682,277636492,547534691,448124242,398985265,301402921,557948552,527710662,918612702,863744231,107320344,432715284,59128024,65727963,676258161,32946934,835822459,770511964,461166116,343408167,17998211,848221697,858591271,46362435,824364831,328202751,365630561,995103238,890456808,94036113,64470646,664862743,990706260,359396629,300623170,692080446,817602348,487784261,244994028,681455875,491580252,412683933,399660699,916003924,760663903,508067130,689273438,91880548,988606621,430502308,579883813,826455005,305040239,767831484,714516765,154715331,845355247,926806355,135516794,91069516,35472257,122231758,793263683,804239605,592967017,672532639,842608090,999978890,231161386,124475657,206273599,594750713,231835184,918601830,681018527,938028426,559281733,105142190,538724427,550388837,173115830,510391703,103666203,501614682,410140830,961906587,300091671,142089919,689410325,38035288,894915766,21299221,932195454,515790513,292647630,791165780,52005883,622988408,228889062,795253257,30755118,943666455,35376090,505952989,664127650,166395022,577426360,326231727,450884898,700174070,408187508,344678438,40090085,70150593,845472926,111658730,333524788,411771824,102230265,197146255,17324111,694514741,135630542,855348505,379769095,250759359,942609877,250317398,957022291,21128807,777057494,157244251,44735678,253263696,290350318,834948642,323676596,249449699,405990727,723580748,814717253,597137899,905586062,968337745,221403249,328224270,727300394,53781812,613277475,580500372,244522461,198280247,748974832,263841288,974280008,954264659,918248017,176934377,264201722,589643305,290974808,593333837,395225438,179994873,162350466,320050372,433045047,366025246,393144514,565643557,8640877,784288899,288900207,85253182,478637325,131263260,114378860,367635955,547043266,778678855,490171167,559533877,254980526,227824717,879654596,77369024,906558511,925397490,79042856,121365524,266854374,868587460,548586492,945874473,638312617,84832085,991194634,770542437,973325827,97213768,222700565,657377812,893006116,783561307,945163345,423802556,793785240,773092094,875738086,470073442,79486028,772801318,283633148,401600674,161425397,804801218,442062120,237610798,352582213,734850396,245130253,823505803,922904684,132125354,718690836,234344855,148969387,910038554,432421722,420198784,226283,655654734,643500159,372504599,562942966,362459458,592487714,852316637,169792569,490918898,241746912,1289860,203840550,711706885,173702405,986044562,319649635,494814298,80203880,952838000,562710321,101867306,125302439,862591722,64454404,391883449,52781994,196226947,598900084,250836877,97971256,275920921,985725374,397507860,885955781,754686616,772514508,758184772,790985353,960031519,998078500,503561361,915720078,639536544,328020351,240495986,244791626,427169108,393366235,351646179,35312487,584461015,239056305,670393176,598896870,196819179,608103651,316364862,767704240,723410504,455415061,322190897,49110370,202741651,569864215,723774463,130023033,99225210,669267907,13853610,347862903,81323587,798905795,934914099,756395372,781310611,417916250,646888060,330898237,571507176,419732579,109158505,114432506,269264277,569637888,214863868,89997447,197077750,865960576,702725113,688399338,78762308,908184004,682275999,243018791,50407390,526920321,874758466,185469278,976362127,588700340,622431229,601799844,594979316,133503580,467236523,644028629,664565301,79544438,961519610,238620173,930257240,945461098,926148511,609529499,658272081,536094601,448059842,109593043,536788222,13824685,216225497,352575933,629302436,122058955,390952378,229635804,460844169,581917301,436528047,715726355,949920216,708617092,576137560,140206597,662715020,401147798,932851631,452234048,753018003,852444650,173823413,665320949,894818492,386415103,488087593,48127658,866170243,79114735,974930808,154842024,472695782,55997821,350518739,413781230,662062202,959632485,733965003,396715631,455864860,646533171,808729755,896990422,382820614,205053086,763446614,825429251,245061937,29823860,324398778,856765760,577253763,365856173,699018250,664178660,23720092,24606480,244249136,46957913,533618851,640318885,798945078,802164902,876150626,168203703,911156869,107610526,428879708,226133024,364657756,32060201,403359966,458053561,924808879,569170945,163908877,387955216,602963020,24146947,110812593,144885758,434436164,917187126,526408516,862786419,834738167,726685496,663630783,759991010,729151292,304074862,368104352,976940704,575425744,61616967,302225093,491291474,854159381,76019919,499965824,615071835,673537834,557051279,125123811,569401064,736551616,127268804,906054994,259743281,818553063,434065737,133871478,208047268,547055960,992026913,80775130,963902162,479982344,114677476,884486351,473275301,851533997,900863971,61049247,350489641,131752566,309736705,244440607,177065138,668923271,309502230,391565154,938627448,889626252,167266950,992513305,665630886,808962357,304343520,588472064,287785213,465880425,119904591,689778629,785669675,666260900,867210842,241109305,22447246,461225297,190579587,173001032,728465364,513101201,545042502,157071590,644810967,135439607,793787607,19895685,172307441,163204731,438275276,16633100,172616168,702507057,171015793,929313265,319480224,795007268,43901642,268006173,899520430,747970708,921903465,130001728,741152075,930750503,645797751,333427697,927447034,958969090,321703473,299426143,901000480,207872363,547889850,122314261,32407957,367170608,108869403,697946133,617955995,548469651,922590011,931362115,187742400,526017935,386237424,796803934,968674624,440877661,12266277,793866005,190047224,815510679,47346799,981679981,771559344,91634022,140211433,536972250,959299634,434705540,356643686,483571825,313542527,577360129,360570957,710201043,634819675,715519429,974103650,137699400,473927981,83708522,80319047,95471191,999979984,249548244,914752895,416477392,86321771,51522050,81141765,683485666,246539237,881979774,147424955,722573694,69029851,336514955,127901065,2068808,410717704,920009670,720265290,133410891,263917569,108851128,597819630,626020744,801236333,302076972,356326896,601733236,622982307,126349555,843127649,142272415,461653303,148646910,785134909,622888395,695454218,893034952,268207959,995970438,787606748,10392106,506928713,676230320,712506894,527530364,35827863,863472281,831623988,73770218,196463116,273225173,568423903,138770796,153527730,212698063,49051164,916676547,328020429,241806932,803024578,292339629,57043914,397829545,204569704,874674859,134791498,638437879,397131941,10336089,565450994,919718183,116210575,88498902,135340768,73062759,191101585,1781761,28769716,934753393,202893277,970758750,902023569,16038588,563566150,453399780,811101482,749395396,96830917,792101240,387391505,511585409,838930122,313912830,713096778,704292517,114470955,915476620,488200163,792608001,314589044,986302172,354333611,312846946,978653566,653231389,923551459,117570897,329110639,592118648,91875316,900672397,136232323,25042115,561989149,511526315,638715842,419383719,540835779,676143549,254146697,98562596,831659135,871507269,229692474,413296859,111173393,766400417,77872391,776713092,456825709,615653138,706079120,77136518,500818885,67566180,151895153,336758766,285170317,466996293,901450313,971259584,936627441,842268377,939894862,716216880,811260725,485330272,802990198,69020038,171587864,599670905,528144964,982496897,823586096,479410557,887566533,909308069,247083631,294191497,969134685,730671947,884898261,953795730,272387833,734657474,150173846,678544497,159195509,627274179,599903330,139544645,274705991,41233334,957383713,800581067,26439545,987801533,577268752,972281365,722810110,747506269,558528133,531310294,495107032,912238346,897103867,934985660,166142521,421587925,872682600,656127768,210869431,734509267,161247513,755567055,744688674,447849202,71355279,972299127,228357466,243632451,272267706,863166632,782527117,536379769,591406055,207248069,792798827,581339401,313697335,238755960,271967124,899230830,175630802,184358236,482948409,573208050,89034486,399482821,73892025,450694787,445440718,187132562,13888904,941049161,143672419,369200414,71101915,801956251,664320563,261200166,327594072,518475774,681177739,111915794,566053564,309693938,673139285]
print(s.findRadius(houses, heaters))